Mathematical Computer Science Seminar
Hemanshu Kaul
IIT
List Coloring Cartesian Products of Graphs: Criticality and the List Color Function
Abstract: The list chromatic number of the Cartesian product of graphs is not well understood. The best result is by Borowiecki, Jendrol, Kral, & 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.
We show how the knowledge of the list color function (list coloring analogue of the chromatic polynomial) can be applied to list coloring of Cartesian products. We introduce the notion of strongly chromatic choosable graphs, that includes odd cycles, cliques, many more infinite families of graphs, and the join of a clique with any other such graph, as a notion of color-criticality in the context of chromatic-choosability. This leads to improved bounds on choosability of Cartesian product of certain large classes of graphs and to classes of chromatic-choosable Cartesian products of graphs. This is joint work with Jeffrey Mudrock.
Monday October 15, 2018 at 3:00 PM in 427 SEO