List coloring the cartesian product of a complete graph and complete bipartite graph
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 where a b, denoted (K n 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 (K n K a,b ) = n + a if and only if b (n + a -1)! a /(a -1)! a ?In this paper, we show the answer to this question is yes by studying (H K a,b ) when H is strongly chromatic-choosable (a special form of vertex criticality related to chromatic choosability) 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 (K a,b ) = 1 + a if and only if b a a .
Authors
- Jeffrey A. Mudrock (ORCID: https://orcid.org/0000-0001-9527-9363)
- Hemanshu Kaul (ORCID: https://orcid.org/0000-0002-6691-0176)
- Leonardo Marciaga
Publication Details
- Journal
- Enumerative Combinatorics and Applications
- Published
- 2025-09-12
- DOI
- https://doi.org/10.54550/eca2026v6s1r5
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00