The -cycle conjecture for chromatic numbers of graph powers
The -cycle conjecture for chromatic numbers of graph powers
Let be a graph of maximum degree at most , and let denote its th power. Suppose that contains no cycle of length as a subgraph. The -cycle conjecture. The largest possible value of the chromatic number , over all such graphs , is
as . The conjecture concerns the threshold immediately below the critical-girth phenomenon of Alon and Mohar and would extend the paper's logarithmic upper-bound results; it remains open in the stated generality.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Ross J. Kang and François Pirot, “Colouring powers and girth”, arXiv:1511.08826 (2016).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.