The List Color Function and Chromatic Choosability

This talk will be accessible to those with knowledge of basic graph theory. The concept of list coloring was introduced independently by Erdös and Vizing in the 1970s. It is a natural generalization of graph coloring with a restricted list of colors for each vertex. Specifically, one seeks to color each vertex of a graph with a color from the corresponding list such that adjacent vertices receive distinct colors. The list chromatic number of a graph is the smallest integer \(k\) for which one can guarantee the existence of such a coloring when the lists all have size at least \(k\). A graph is said to be chromatic choosable when its list chromatic number equals its typical chromatic number. Recently, the speaker introduced the notion of strongly chromatic choosable graphs which is a special type of chromatic choosable graph that includes odd cycles, cliques, join of a clique with any other such graph, and many more families of graphs.

The list chromatic number of the Cartesian product of graphs is not well understood. The best result is by Borowiecki, Jendrol, Kral, and Miskuf (2006) who proved that the list chromatic number of the Cartesian product of two graphs can be bounded in terms of the list chromatic number and the coloring number of the factors, implying a bound exponential in the list chromatic number of the factors. The focus of this talk is on improving upon these results in the case where one has the Cartesian product of a strong \(k\)-chromatic choosable graph and a complete bipartite graph. In particular, the speaker will completely characterize the list chromatic number of a strong \(k\)-chromatic choosable graph and a star, and the speaker will present two generalizations of this result. The main tool in proving the results is the list color function of a graph which is a list version of the chromatic polynomial of a graph. No previous knowledge of the chromatic polynomial or the list color function will be assumed.

Event Topic

Discrete Applied Math Seminar