Chen--Lih--Wu's equitable Brooks conjecture

Let GG be a connected finite graph of maximum degree Δ1\Delta \geqslant 1. An equitable Δ\Delta-coloring is a proper coloring with Δ\Delta color classes whose sizes differ by at most 11.

Chen--Lih--Wu's conjecture. The graph GG has an equitable Δ\Delta-coloring unless one of the following holds: Δ=2\Delta=2 and GG is an odd cycle; GKΔ+1G \cong K_{\Delta+1}; or Δ\Delta is odd and GKΔ,ΔG \cong K_{\Delta,\Delta}.

This is an equitable analogue of Brooks's theorem. The conjecture remains open, and the paper studies measurable and Borel versions of related coloring results.

Sources & referencesView supporting material

Primary source

Anton Bernshteyn and Clinton T. Conley, “Equitable Colorings of Borel Graphs”, arXiv:1908.10475 (2021).

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.