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:
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>=k. The answer has been determined in terms of maximum
degree for several classes of graphs. We have a general upper bound
in terms of maximum degree and tree-width. (The tree-width
of a graph measures how far away it is from being a tree, in some sense.)
We will discuss the concepts and sketch a couple proofs.