Kostochka–Nakprasit equitable coloring conjecture for d-degenerate graphs

Let Δ\Delta be an integer, let d{2,,Δ}d\in\{2,\dotsc,\Delta\}, and let GG be a dd-degenerate graph with maximum degree at most Δ\Delta. 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 GG admits an equitable kk-coloring whenever

kΔ+d+12.k\geqslant\frac{\Delta+d+1}{2}.

This generalizes the authors' earlier conjecture for 22-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 K4K_4-minor-free graphs does not settle the conjecture for all dd-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

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.