Abstract.
The achromatic index of a graph G is the maximum number of colours that can be assigned to edges of G in such a way that the colouring is proper and any two colours meet on two adjacent edges. To compute the achromatic index of complete graphs seems to be a very difficult task. Indeed, that knowledge would yield all odd projective plane orders. The aim of the paper is to establish a nontrivial lower bound of the achromatic index of for a prime q≥7.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Acknowledgments The first author gratefully acknowledges a support of the Slovak grant VEGA 1/7467/20. The authors wish to thank to an anonymous referee for an easy proof of Lemma 8.
Final version received: November 10, 2003
Rights and permissions
About this article
Cite this article
Horňák, M., Pčola, Š. & Woźniak, M. On the Achromatic Index of for a Prime q . Graphs and Combinatorics 20, 191–203 (2004). https://doi.org/10.1007/s00373-004-0550-7
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00373-004-0550-7