Total Equitable List Coloring

Abstract

An equitable coloring is a proper coloring of a graph such that the sizes of the color classes differ by at most one. A graph $G$ is equitably $k$-colorable if there exists an equitable coloring of $G$ which uses $k$ colors, each one appearing on either $\lfloor |V(G)|/k\rfloor$ or $\lceil |V(G)|/k\rceil$ vertices of $G$. In 1994, Fu conjectured that for any simple graph $G$, the total graph of $G$, $T(G)$, is equitably $k$-colorable whenever $k\ge \max \{\chi (T(G)),\Delta (G)+2\}$ where $\chi (T(G))$ is the chromatic number of the total graph of $G$ and $\Delta (G)$ is the maximum degree of $G$. We investigate the list coloring analogue. List coloring requires each vertex $v$ to be colored from a specified list $L(v)$ of colors. A graph is $k$-choosable if it has a proper list coloring whenever vertices have lists of size $k$. A graph is equitably $k$-choosable if it has a proper list coloring whenever vertices have lists of size $k$, where each color is used on at most $\lceil |V(G)|/k\rceil$ vertices. In the spirit of Fu's conjecture, we conjecture that for any simple graph $G$, $T(G)$ is equitably $k$-choosable whenever $k\ge \max \{{\chi }_l(T(G)),\Delta (G)+2\}$ where ${\chi }_l(T(G))$ is the list chromatic number of $T(G)$. We prove this conjecture for all graphs satisfying $\Delta (G)\le 2$ while also studying the related question of the equitable choosability of powers of paths and cycles.

13 pages