The 2t+22t+2-cycle conjecture for chromatic numbers of graph powers

From papers

Let GG be a graph of maximum degree at most dd, and let GtG^t denote its ttth power. Suppose that GG contains no cycle of length 2t+22t+2 as a subgraph. The 2t+22t+2-cycle conjecture. The largest possible value of the chromatic number χ(Gt)\chi(G^t), over all such graphs GG, is

Θ(dt/logd)\Theta(d^t/\log d)

as dd\to\infty. 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

No solutions have been posted yet.