
arXiv: 1803.07450
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 \geq \max\{��(T(G)), ��(G)+2\}$ where $��(T(G))$ is the chromatic number of the total graph of $G$ and $��(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 \geq \max\{��_l(T(G)), ��(G)+2\}$ where $��_l(T(G))$ is the list chromatic number of $T(G)$. We prove this conjecture for all graphs satisfying $��(G) \leq 2$ while also studying the related question of the equitable choosability of powers of paths and cycles.
13 pages
list coloring, equitable coloring, Coloring of graphs and hypergraphs, total coloring, graph coloring, FOS: Mathematics, equitable choosability, Mathematics - Combinatorics, O5C15, Combinatorics (math.CO)
list coloring, equitable coloring, Coloring of graphs and hypergraphs, total coloring, graph coloring, FOS: Mathematics, equitable choosability, Mathematics - Combinatorics, O5C15, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
