Strengthened Chen–Lih–Wu and Kostochka–Pelsmajer–West conjecture

About 3 years old · traced to

Let GG be an rr-colorable graph, with maximum degree Δ(G)≤r\Delta(G)\leq r. Let an rr-list assignment LL assign rr available colors to each vertex, and call GG equitably rr-choosable if every such assignment has a proper list coloring using each color at most ⌈∣V(G)∣/r⌉\left\lceil |V(G)|/r\right\rceil times. A coloring is SE rr-choosable when it satisfies the stronger size condition defined in the paper: all color classes have size at most ⌈∣V(G)∣/r⌉\left\lceil |V(G)|/r\right\rceil, with at most ∣V(G)∣mod⁡∗r|V(G)|\mathbin{\operatorname{mod}^*}r classes attaining that upper bound. Strengthened conjecture. Either rr is odd and Kr,r⊆GK_{r,r}\subseteq G, or GG is equitably rr-choosable and even SE rr-choosable. The statement is proposed in the concluding remarks as a possible strengthening; it is not claimed to be proved, and its status is open.

References

Primary source

H. A. Kierstead, Alexandr Kostochka and Zimu Xiang, “Equitable list coloring of planar graphs with given maximum degree”, arXiv:2309.00989 (2023).

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.