Bonamy–Bousquet's conjecture on color savings for graph powers
Let be a graph with maximum degree , let , and let denote its -th power. Write for the corresponding upper-bound function on the number of colors.
Bonamy–Bousquet's conjecture. For every , only finitely many graphs satisfy
This conjecture proposes that, apart from finitely many exceptional graphs for each , one can spare colors from the naive upper bound for coloring graph powers. It strengthens the known result that for , .
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.