Discrete Applied Mathematics Seminar by Leonardo Marciaga: List Coloring the Cartesian Product of a Complete Graph and a Complete Bipartite Graph

Speaker: Leonardo Marciaga, research assistant, Illinois Tech

Title: List Coloring the Cartesian Product of a Complete Graph and a Complete Bipartite Graph

Abstract:

List coloring, introduced independently by Vizing, and Erdős, Rubin, and Taylor, is a generalization of the classical notion of graph coloring. While the chromatic number of the Cartesian product of two graphs is known, the list chromatic number of the Cartesian product of two graphs is not nearly as well understood. In this talk, we focus our study on the list chromatic number of the Cartesian product of a complete graph and a complete bipartite graph. More specifically, we answer positively the following question: for each positive integer a, does \(\chi_{\ell}(K_n \square K_{a,b}) = n+a\) if and only if \(b \geq (n+a-1)!^a/(a-1)!^a\)? On one hand, we prove properties relating to the Cartesian product of complete bipartite graphs and strongly chromatic-choosable graphs (a special form of vertex criticality). On the other hand, we also prove several technical, enumerative lemmas with the help of the list color function and analytic inequalities, including Karamata's, to aid our study. Our result can be viewed as a generalization of the well-known result that \(\chi_{\ell}(K_{a,b}) = 1+a\) if and only if \(b \geq a^a\).

This is joint work with Hemanshu Kaul and Jeff Mudrock.

Discrete Applied Math seminar