Bonamy–Bousquet's conjecture on color savings for graph powers

From papers

Let GG be a graph with maximum degree Δ\Delta, let k2k\geqslant 2, and let GkG^k denote its kk-th power. Write f(k,Δ)f(k,\Delta) for the corresponding upper-bound function on the number of colors.

Bonamy–Bousquet's conjecture. For every k2k\geqslant 2, only finitely many graphs GG satisfy

χ(Gk)f(k,Δ)+1k.\chi(G^k)\geqslant f(k,\Delta)+1-k.

This conjecture proposes that, apart from finitely many exceptional graphs for each kk, one can spare kk colors from the naive upper bound for coloring graph powers. It strengthens the known result that for k3k\geqslant 3, χ(Gk)f(k,Δ)1\chi(G^k)\leqslant f(k,\Delta)-1.

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

Théo Pierron, “A Brooks-like result for graph powers”, arXiv:1912.11181 (2019).

Solutions 0

No solutions have been posted yet.