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.
References
Primary source
Ross J. Kang and François Pirot, “Colouring powers and girth”, arXiv:1511.08826 (2016).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.