The Δ\Delta-Equitable Coloring Conjecture

About 8 years old · traced to

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.

References

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.