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

Abstract

We study the list chromatic number of the Cartesian product of a complete graph of order $n$ and a complete bipartite graph with partite sets of size $a$ and $b$, denoted ${\chi }_{\ell }(K_n\square K_{a,b})$. At the 2024 Sparse Graphs Coalition's Workshop on algebraic, extremal, and structural methods and problems in graph colouring, Mudrock presented the following question: For each positive integer $a$, does ${\chi }_{\ell }(K_n\square K_{a,b})=n+a$ if and only if $b\ge (n+a-1){!}^a/(a-1){!}^a$? In this paper, we show the answer to this question is yes by studying ${\chi }_{\ell }(H\square K_{a,b})$ when $H$ is strongly chromatic-choosable (a special form of vertex criticality) with the help of the list color function and analytic inequalities such as that of Karamata. 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\ge a^a$.

16 pages