On chromatic indices of finite affine spaces

Gabriela Araujo-Pardo, György Kiss, Christian Rubio-Montiel, Adrián Vázquez-Ávila


A line-coloring of the finite affine space AG(n, q) is proper if any two lines from the same color class have no point in common, and it is complete if for any two different colors i and j there exist two intersecting lines, one is colored by i and the other is colored by j. The pseudoachromatic index of AG(n, q), denoted by ψ′(AG(n, q)),  is the maximum number of colors in any complete line-coloring of AG(n, q). When the coloring is also proper, the maximum number of colors is called the achromatic index of AG(n, q). We prove that ψ′(AG(n, q)) ∼ q1.5n − 1 for even n, and that q1.5(n − 1) < ψ′(AG(n, q)) < q1.5n − 1 for odd n. Moreover, we prove that the achromatic index of AG(n, q) is q1.5n − 1 for even n, and we provide the exact values of both indices in the planar case.


Achromatic index, complete coloring, finite affine space, pseudoachromatic index

Full Text:


DOI: https://doi.org/10.26493/1855-3974.1546.c5e

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications