Strong Chen–Lih–Wu decomposition conjecture

Let k3k\geq3, and let a kk-decomposition of a graph be a partition of its vertex set into induced subgraphs that are kk-basic. Strong Chen–Lih–Wu conjecture. If GG is a kk-colorable graph with Δ(G)=k\Delta(G)=k, then GG has no equitable kk-coloring if and only if kk is odd and there exists HGH\subseteq G such that H=Kk,kH=K_{k,k} and GHG-H has a kk-decomposition. This is presented as a strengthening intended to describe all non-equitably colorable graphs in the stated class.

Sources & referencesView supporting material

Primary source

H. A. Kierstead, Alexandr Kostochka and Zimu Xiang, “Results and Problems on Equitable Coloring of Graphs”, arXiv:2504.14711 (2025).

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.