The -Equitable Coloring Conjecture
The -Equitable Coloring Conjecture
Let be a connected finite simple graph, and let denote its maximum vertex degree. Write for the complete graph on vertices, for an odd cycle, and for the complete bipartite graph with parts of size .
The -ECC. is equitably -colorable if it is different from , , and .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.