Kostochka–Nakprasit equitable coloring conjecture for d-degenerate graphs
Kostochka–Nakprasit equitable coloring conjecture for d-degenerate graphs
Let be an integer, let , and let be a -degenerate graph with maximum degree at most . An equitable coloring is a proper vertex coloring in which the color classes have sizes differing by at most one. Kostochka–Nakprasit's conjecture. The graph admits an equitable -coloring whenever
This generalizes the authors' earlier conjecture for -degenerate graphs and would extend equitable-coloring results known for series-parallel and outerplanar graphs. The source presents it as an open problem; the stated theorem for -minor-free graphs does not settle the conjecture for all -degenerate graphs.
Sources & referencesView supporting material
Primary source
Rémi De Joannis de Verclos and Jean-Sébastien Sereni, “Equitable Colorings of K\_4-minor-free Graphs”, arXiv:1703.02250 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.