Strong equitable Brooks conjecture

Let GG be a graph. A graph is kk-equitable if G=ks|G|=ks, χ(G)k\chi(G)\le k, and every proper kk-coloring of GG has ss vertices in each color class. Write H1+H2H_1+H_2 for the disjoint union of graphs H1H_1 and H2H_2. Strong equitable Brooks conjecture. Every graph GG with χ(G),Δ(G)k\chi(G), \Delta(G)\le k has no equitable kk-coloring if and only if kk is odd and G=H+Kk,kG=H+K_{k,k} for some kk-equitable graph HH. This is presented as a strengthening of the Chen–Lih–Wu conjecture; the cited results leave cases with k5k\ge5 and at least five color classes unresolved.

Sources & referencesView supporting material

Primary source

H. A. Kierstead, A. V. Kostochka and E. C. Yeager, “On the Corrádi-Hajnal Theorem and a question of Dirac”, arXiv:1601.03791 (2016).

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.