The Δ\Delta-Equitable Coloring Conjecture

Let GG be a connected finite simple graph, and let Δ(G)\Delta(G) denote its maximum vertex degree. Write KmK_m for the complete graph on mm vertices, C2m+1C_{2m+1} for an odd cycle, and K2m+1,2m+1K_{2m+1,2m+1} for the complete bipartite graph with parts of size 2m+12m+1.

The Δ\Delta-ECC. GG is equitably Δ(G)\Delta(G)-colorable if it is different from KmK_m, C2m+1C_{2m+1}, and K2m+1,2m+1K_{2m+1,2m+1}.

The conjecture is a list analogue of Brooks's theorem for equitable coloring. It has been proved for interval graphs, trees, outerplanar graphs, subcubic graphs, and several other graph classes.

Sources & referencesView supporting material

Primary source

Hemanshu Kaul, Jeffrey A. Mudrock, Michael J. Pelsmajer and Benjamin Reiniger, “Proportional Choosability: A New List Analogue of Equitable Coloring”, arXiv:1806.06966 (2018).

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.