TOPICS
Search

Achromatic Number


The achromatic number chi_a(G) of a finite simple graph G is the greatest number of colors in a proper vertex coloring such that every pair of distinct colors occurs at the ends of some graph edge. A proper vertex coloring alone would allow a different color on every graph vertex. Consequently chi(G)<=chi_a(G), where chi(G) is the chromatic number.

Timmons (2026) proved that the Peisert graph of order q=p^(2r), where p is a prime number with p=3  (mod4), has chi_a=(q+1)/2 for all sufficiently large admissible q. For a fixed integer k>=3 and sufficiently large prime power q=1  (mod2k), the Cayley graph on the finite field F_q joining pairs whose difference is a nonzero kth power satisfies chi_a>=(q-1)/k+1. Timmons (2026) credits ChatGPT with mathematical proof assistance.


See also

Chromatic Number, Vertex Coloring

Explore with Wolfram|Alpha

References

Edwards, K. "The Harmonious Chromatic Number and the Achromatic Number." In Surveys in Combinatorics, 1997 (Ed. R. A. Bailey). Cambridge, England: Cambridge University Press, pp. 13-48, 1997. https://doi.org/10.1017/CBO9780511662119.003.Farber, M.; Hahn, G.; Hell, P.; and Miller, D. "Concerning the Achromatic Number of Graphs." J. Combin. Th. Ser. B 40, 21-39, 1986. https://doi.org/10.1016/0095-8956(86)90062-6.Harary, F. and Hedetniemi, S. "The Achromatic Number of a Graph." J. Combin. Th. 8, 154-161, 1970. https://doi.org/10.1016/S0021-9800(70)80072-2.Kortsarz, G. and Krauthgamer, R. "On Approximating the Achromatic Number." SIAM J. Discr. Math. 14, 408-422, 2001. https://doi.org/10.1137/S0895480100379579.Timmons, C. "The Achromatic Number of Paley Graphs, Peisert Graphs, and Related Cayley Graphs." 20 Oct 2026. https://arxiv.org/abs/2610.27510.Yannakakis, M. and Gavril, F. "Edge Dominating Sets in Graphs." SIAM J. Appl. Math. 38, 364-372, 1980. https://doi.org/10.1137/0138030.

Cite this as:

Weisstein, Eric W. "Achromatic Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AchromaticNumber.html

Subject classifications