The List Equitable Total Coloring Conjecture

For a simple graph $G$, the List Equitable Total Coloring Conjecture of Kaul, Mudrock, and Pelsmajer (2018) asserts that the total graph $T(G)$ (the graph on the vertices and edges of $G$, with adjacency meaning adjacency or incidence in $G$) is equitably $k$-choosable for every integer $k \ge \max\{\chi_l(T(G)), \Delta(G)+2\}$; that is, whenever every element of $G$ is given a list of $k$ colors, there is a proper coloring of the vertices and edges from their lists in which no color is used on more than $\lceil(|V(G)|+|E(G)|)/k\rceil$ elements. The conjecture is the list analogue of Fu's 1994 Equitable Total Coloring Conjecture and is known only for graphs of maximum degree at most 2 and, per the source paper's remark and follow-up work, for trees of maximum degree 3, stars, double stars, subdivisions of stars, and generalized theta graphs. The problem is open in general: no proof, refutation, or general bound appears in the literature through 2026.

Background

A total coloring of a graph $G$ assigns colors to both the vertices and the edges so that adjacent vertices, adjacent edges, and incident vertex–edge pairs receive distinct colors; the minimum number of colors needed is the total chromatic number $\chi''(G)$. Total coloring is equivalent to ordinary vertex coloring of the total graph $T(G)$: the graph whose vertex set is $V(G) \cup E(G)$, where two elements are adjacent in $T(G)$ exactly when they are adjacent or incident in $G$; thus $\chi''(G) = \chi(T(G))$ and $\Delta(T(G)) = 2\Delta(G)$, where $\Delta$ denotes maximum degree. The classical Total Coloring Conjecture of Behzad and Vizing asserts $\chi''(G) \le \Delta(G)+2$ and remains open. An equitable coloring is a proper coloring in which the sizes of any two color classes differ by at most one; the Hajnal–Szemerédi theorem guarantees an equitable $k$-coloring for every $k \ge \Delta(G)+1$. In 1994, Fu conjectured the total analogue: for every simple graph $G$, the total graph $T(G)$ is equitably $k$-colorable for each $k \ge \max\{\chi(T(G)), \Delta(G)+2\}$ (the term $\Delta(G)+2$ is necessary because Fu exhibited an infinite family with $\chi''(G) = \Delta(G)+1$ admitting no equitable total $(\Delta(G)+1)$-coloring). List coloring, introduced by Vizing and by Erdős, Rubin, and Taylor, equips each vertex with a list $L(v)$ of allowed colors and requires the coloring to respect the lists; a graph is $k$-choosable if it is properly colorable from every assignment of lists of size $k$, and $\chi_l$ denotes the list chromatic number, the least such $k$. In 2003, Kostochka, Pelsmajer, and West introduced the equitable version: a graph is equitably $k$-choosable if, for every assignment of lists of $k$ colors, there is a proper list coloring in which each color is used on at most $\lceil|V|/k\rceil$ vertices. They conjectured (still open) that every graph is equitably $k$-choosable for $k \ge \Delta+1$. In this landscape, Kaul, Mudrock, and Pelsmajer (2018) posed the list analogue of Fu's conjecture: the List Equitable Total Coloring Conjecture, that for every simple graph $G$, the total graph $T(G)$ is equitably $k$-choosable for each $k \ge \max\{\chi_l(T(G)), \Delta(G)+2\}$. The conjecture is sharp if true, since Fu's extremal family also witnesses total graphs that are not equitably $(\Delta(G)+1)$-choosable. Restricted to uniform list assignments (every element receiving the same list), the conjecture yields, for every $k \ge \max\{\chi_l(T(G)), \Delta(G)+2\}$, a proper total $k$-coloring from the common list in which each color is used on at most $\lceil(|V(G)|+|E(G)|)/k\rceil$ elements — the ceiling convention that defines equitable choosability, and a weaker requirement than the differ-by-one convention of Fu's conjecture, which additionally forces every color class to have size at least $\lfloor(|V(G)|+|E(G)|)/k\rfloor$; the source accordingly presents the conjecture as the list analogue of Fu's in spirit, not as a formal implication of it. When $\chi_l(T(G))$ exceeds that threshold, the list conjecture is silent about the gap range, since equitable colorability is not monotone in $k$. Note also that, by the Hajnal–Szemerédi theorem, Fu's conjecture is automatic for $k \ge 2\Delta(G)+1$, whereas the list conjecture is open even in that range, where it becomes the Kostochka–Pelsmajer–West conjecture restricted to total graphs.

Problem Statement

Prove or refute the List Equitable Total Coloring Conjecture of Kaul, Mudrock, and Pelsmajer: for every simple graph $G$ with total graph $T(G)$ (the graph on $V(G) \cup E(G)$ with adjacency meaning adjacency or incidence in $G$) and every integer $k \ge \max\{\chi_l(T(G)), \Delta(G)+2\}$, where $\chi_l(T(G))$ is the list chromatic number of $T(G)$ (the least $k$ such that $T(G)$ is properly colorable from every assignment of lists of $k$ colors) and $\Delta(G)$ is the maximum degree of $G$, the graph $T(G)$ is equitably $k$-choosable — that is, for every assignment of a list of $k$ colors to each element of $V(G) \cup E(G)$ (a $k$-assignment), there exists a proper coloring of the vertices and edges of $G$ from these lists (adjacent vertices, adjacent edges, and incident vertex–edge pairs receive distinct colors) such that each color is used on at most $\lceil(|V(G)|+|E(G)|)/k\rceil$ elements. Equivalently, in the form used by the follow-up literature: every total graph $T$ of a simple graph is equitably $k$-choosable for each $k \ge \max\{\chi_l(T), \Delta(T)/2+2\}$. The conjecture is currently verified only for graphs with $\Delta(G) \le 2$, trees of maximum degree 3, stars, double stars, subdivisions of stars, and generalized theta graphs; the problem asks for the general statement over all simple graphs. A valid refutation is an explicit graph $G$, an integer $k$ with $k \ge \max\{\chi_l(T(G)), \Delta(G)+2\}$, and a $k$-assignment for the elements of $G$ admitting no proper equitable list coloring of $T(G)$.

References

1. H. Kaul, J. A. Mudrock, M. J. Pelsmajer, "Total Equitable List Coloring", Graphs and Combinatorics 34(6) (2018) 1637–1649; arXiv:1803.07450. DOI: 10.1007/s00373-018-1965-x, https://arxiv.org/abs/1803.07450 (source of Conjecture 9 and Theorem 14)
2. M. Marsh, J. A. Mudrock, T. Wagstrom, "On list equitable total colorings of the generalized theta graph", Discussiones Mathematicae Graph Theory 41(4) (2021) 1215–1233; arXiv:1908.01657. DOI: 10.7151/dmgt.2292, https://arxiv.org/abs/1908.01657 (verifies the conjecture for subdivisions of stars and generalized theta graphs)
3. H.-L. Fu, "Some results on equalized total coloring", Congressus Numerantium 102 (1994) 111–119. Zbl 0837.05062, https://zbmath.org/?q=an%3A0837.05062 (origin of the non-list Equitable Total Coloring Conjecture and of the sharpness example)
4. A. V. Kostochka, M. J. Pelsmajer, D. B. West, "A list analogue of equitable coloring", Journal of Graph Theory 44(3) (2003) 166–177. DOI: 10.1002/jgt.10137, https://doi.org/10.1002/jgt.10137 (introduction of equitable choosability and of the $k \ge \Delta+1$ conjecture)
5. O. V. Borodin, A. V. Kostochka, D. R. Woodall, "List Edge and List Total Colourings of Multigraphs", Journal of Combinatorial Theory, Series B 71(2) (1997) 184–204. DOI: 10.1006/jctb.1997.1780, https://doi.org/10.1006/jctb.1997.1780 (the List Total Coloring Conjecture: total graphs are chromatic-choosable)
6. H. A. Kierstead, A. Kostochka, Z. Xiang, "Equitable List Coloring of Planar Graphs With Given Maximum Degree", Journal of Graph Theory 108(4) (2024) 832–838. DOI: 10.1002/jgt.23203, https://doi.org/10.1002/jgt.23203 (the parent equitable-choosability conjecture remains open; proved for planar graphs with given maximum degree)
7. H. A. Kierstead, A. Kostochka, Z. Xiang, "Equitable list coloring of sparse graphs", Discrete Mathematics 349(5) (2026), article 114981. DOI: 10.1016/j.disc.2026.114981, https://doi.org/10.1016/j.disc.2026.114981 (ongoing partial progress on the equitable-choosability conjecture for sparse graphs)