List Coloring a Cartesian Product with a Complete Bipartite Factor

List coloring, a variation on the typical vertex coloring problem, was introduced independently by Vizing and by Erdos, Rubin, and Taylor in the 1970’s. In list coloring the vertices of a graph are each assigned a list of colors, a so called list assignment. For a given list assignment, we seek a proper coloring of the graph such that the color we use on each vertex comes from the list associated with the vertex. The list chromatic number of a graph is the smallest integer k such that the graph has a proper list-coloring for any list assignment that assigns lists of size k to each vertex in the graph.

Our work is motivated by a classic result demonstrating that complete bipartite graphs can have arbitrarily large list chromatic number (far from their chromatic number of 2). Here we study the list chromatic number of the Cartesian product of a graph with a complete bipartite graph and when it is as large as possible, far from its chromatic number. We prove tight bounds, improving previously known best results. We also present interesting results in the case that G is strongly chromatic-choosable which is a notion of criticality that was recently introduced by H. Kaul and the presenter. Our main tool for obtaining results is the list color function which is a list analogue of the chromatic polynomial. This is joint work with Hemanshu Kaul.

Event Topic

Discrete Applied Math Seminar