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

About 7 years old · traced to

Let GG be a graph with maximum degree Δ\Delta, let k⩾2k\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 k⩾2k\geqslant 2, only finitely many graphs GG satisfy

χ(Gk)⩾f(k,Δ)+1−k.\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 k⩾3k\geqslant 3, χ(Gk)⩽f(k,Δ)−1\chi(G^k)\leqslant f(k,\Delta)-1.

References

Primary source

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

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.