Equitably k-Choosable Graphs

Abstract

A proper coloring of a graph G assigns colors to the vertices such that no two adjacent vertices have the same color. We discuss two generalizations of graph vertex coloring and a common generalization of them.

For each vertex v in a graph, let L(v) be a list of colors available for v. A graph is k-choosable if whenever each vertex v is assigned a list L(v) of size k, there is a proper coloring f such that f(v) is chosen from L(v) (for each vertex v).

A proper coloring of a graph G is equitable if the sizes of the color classes differ by at most 1. A graph is equitably k-colorable if it has an equitable coloring that uses exactly kcolors.

A graph is equitably k-choosable if for every assignment of lists of size k to its vertices, there is a proper coloring chosen from the lists such that each color class has size at most $\lceil n/k \rceil$. This combines the notions of k-choosability and equitable k-colorability.

We seek the least k such that G is equitably j-choosable for all $j\ge k$. We have solved this for trees, interval graphs, and graphs with maximum degree 3. We also have an upper bound on it for outerplanar graphs in terms of maximum degree. We will discuss the concepts, sketch some proofs, and describe a general technique. ( this is work with A.V. Kostochka and D.B. West)