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

At least 6 years old · documented by

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; G≅KΔ+1G \cong K_{\Delta+1}; or Δ\Delta is odd and G≅KΔ,Δ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.

References

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.