The list Δ\Delta-Equitable Coloring Conjecture

Let GG be a connected finite simple graph. A list assignment LL assigns a list of colors to each vertex; it is a kk-assignment when L(v)=k|L(v)|=k for every vV(G)v\in V(G). An equitable LL-coloring is a proper coloring using colors from the lists such that each color appears on at most V(G)/k\lceil |V(G)|/k\rceil vertices. The graph is equitably kk-choosable when it has an equitable LL-coloring for every kk-assignment LL. Let KmK_m, C2m+1C_{2m+1}, and K2m+1,2m+1K_{2m+1,2m+1} denote respectively a complete graph, an odd cycle, and a complete bipartite graph with parts of size 2m+12m+1.

List Δ\Delta-ECC. GG is equitably kk-choosable for each kΔ(G)k\geq\Delta(G) if it is different from KmK_m, C2m+1C_{2m+1}, and K2m+1,2m+1K_{2m+1,2m+1}.

This is the list-context analogue of the Δ\Delta-Equitable Coloring Conjecture. The source presents it as a conjecture attributed to KP03, but gives no evidence of a resolution.

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.