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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

List coloring the cartesian product of a complete graph and complete bipartite graph

Jeffrey A. Mudrock, Hemanshu Kaul, Leonardo Marciaga
Enumerative Combinatorics and Applications
Advanced Graph Theory Research
article

List coloring the cartesian product of a complete graph and complete bipartite graph

Jeffrey A. Mudrock, Hemanshu Kaul, Leonardo Marciaga
article en

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 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 .

Enumerative Combinatorics and ApplicationsVol. 6(1)
Openalex Percentile: Top 65%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.