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 k colors.
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 ceiling of n/k. 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 > k. We have solved this for trees, interval graphs, and graphs with maximum degree 3. We have a general upper bound which is linear with respect to maximum degree plus tree-width. We will discuss the concepts, sketch some proofs, and describe a general technique.
Joint work with A.V.Kostochka and D.B.West