On the List Chromatic Number of the Cartesian Product with a Traceable Graph: Using the Alon-Tarsi Method

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 restricted list colors for each vertex. For example, consider a graph where vertices correspond to radio transmitters and edges indicate interference. Colors correspond to radio frequencies, and each transmitter has a finite list of acceptable frequencies associated with it. Is it possible to assign a frequency to each transmitter so that interfering transmitters are assigned different frequencies? This talk will be accessible to students with just a basic background in graph theory. The speaker will introduce and discuss all advanced topics in the talk. The focus will be on the Alon-Tarsi method, an algebraic tool, for list coloring and its application to Cartesian products of graphs.

The list coloring 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 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. They conjecture that the bound can be improved to a constant times the sum of the list chromatic numbers. With this in mind, the speaker studies the list coloring of the Cartesian product of an odd cycle or complete graph with a traceable graph (i.e. a graph containing a Hamilton path). He shows families of graphs where his result improves upon known bounds for the list chromatic number. This is joint work with Hemanshu Kaul.

Event Topic

Discrete Applied Math Seminar