2018/03/20 by Kaul, Hemanshu, Mudrock, Jeffrey A., Pelsmajer, Michael J.
#Combinatorics (math.CO) #FOS: Mathematics #O5C15
paper · doi:10.48550/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 ≥ 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 ≥ 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) ≤ 2 while also studying the related question of the equitable choosability of powers of paths and cycles.