Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 47 min ago
PreprintarXiv licencearXiv

The achromatic number of Paley graphs, Peisert graphs, and related Cayley graphs

  • Craig Timmons
Open at sourcePDFDOICite

Abstract

The achromatic number of a graph G, denoted χa (G), is the maximum number of colors in a proper vertex coloring of G. Generalizing a result of Maistrelli and Penman, we prove that for sufficiently large q, the achromatic number of the k-th power Paley graph is at least (q−1)/k + 1. This lower bound gives the correct order of magnitude in q, but determining the correct dependence on k remains open for all k ≥ 3. The achromatic number of Peisert graphs is shown to be (q+1)/2. These bounds are consequences of a general theorem involving Cayley graphs whose generating set is a union of cyclotomic classes. Using character sums and Weil's bound, we prove an upper bound that improves the standard trivial bound binom χa (G) 2 ≤ e(G). Finally, we consider random Cayley-sum graphs on an abelian group Γ of order n, where elements are included in the generating set independently with probability 1/2. We prove that the achromatic and pseudochromatic number of such a graph are both at most ((√3+o(1))n)/(√(log2 n)) with high probability.

Related

  1. Minimal Cayley graphs with large chromatic number
    James Davies, Meike Hatzel, Liana Yepremyan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. Odd-ordered Cayley graphs satisfy Erdős--Gyárfás
    Michael C. Burkhart
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. COLORING SEMIMINIMAL CAYLEY GRAPHS
    Ignacio Garc Ía-Marco, Kolja Knauer, Giuliamaria Menara
    HALPreprintCC BY 4.0Full textGeneral mathematicsHAL
  4. On Edge-Primitive $2$-Arc-Transitive (Bi-)Cayley Graphs
    Hao Nan Chen, Jing Jian Li, Ji Cheng Ma +1
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  5. Composing group automorphisms with colour-preserving automorphisms of Cayley graphs
    Dave Witte Morris
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{timmons2026achromatic,
  title = {{The achromatic number of Paley graphs, Peisert graphs, and related Cayley graphs}},
  author = {Craig Timmons},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.27510},
  eprint = {2610.27510},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.27510},
}
RIS
TY  - UNPB
TI  - The achromatic number of Paley graphs, Peisert graphs, and related Cayley graphs
AU  - Craig Timmons
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.27510
UR  - https://arxiv.org/abs/2610.27510
AB  - The achromatic number of a graph G, denoted χ_a (G), is the maximum number of colors in a proper vertex coloring of G. Generalizing a result of Maistrelli and Penman, we prove that for sufficiently large q, the achromatic number of the k-th power Paley graph is at least (q−1)/k + 1. This lower bound gives the correct order of magnitude in q, but determining the correct dependence on k remains open for all k ≥ 3. The achromatic number of Peisert graphs is shown to be (q+1)/2. These bounds are consequences of a general theorem involving Cayley graphs whose generating set is a union of cyclotomic classes. Using character sums and Weil's bound, we prove an upper bound that improves the standard trivial bound binom χ_a (G) 2 ≤ e(G). Finally, we consider random Cayley-sum graphs on an abelian group Γ of order n, where elements are included in the generating set independently with probability 1/2. We prove that the achromatic and pseudochromatic number of such a graph are both at most ((√3+o(1))n)/(√(log_2 n)) with high probability.
ER  -