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

About 11 years old · traced to

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/log⁡d)\Theta(d^t/\log d)

as d→∞d\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.

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.