Bonamy–Bousquet's conjecture on color savings for graph powers
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 , .
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
Sign in to submit a solution.
No solutions have been posted yet.