2018/11/02 by Kaul, Hemanshu, Mudrock, Jeffrey A. · 2 citations
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1811.02420
We study the list chromatic number of the Cartesian product of any graph G and a complete bipartite graph with partite sets of size a and b, denoted χ_ℓ(G \square Ka,b). We have two motivations. A classic result on the gap between list chromatic number and the chromatic number tells us χ_ℓ(Ka,b) = 1 + a if and only if b ≥ aa. Since χ_ℓ(Ka,b) ≤ 1 + a for any b ∈ ℕ, this result tells us the values of b for which χ_ℓ(Ka,b) is as large as possible and far from χ(Ka,b)=2. In this paper we seek to understand when χ_ℓ(G \square Ka,b) is far from χ(G \square Ka,b) = max \χ(G), 2 \. It is easy to show χ_ℓ(G \square Ka,b) ≤ χ_ℓ (G) + a. In 2006, Borowiecki, Jendrol, Král, and Miskuf showed that this bound is attainable if b is sufficiently large; specifically, χ_ℓ(G \square Ka,b) = χ_ℓ (G) + a whenever b ≥ (χ_ℓ(G) + a - 1)a|V(G)|. Given any graph G and a ∈ ℕ, we wish to determine the smallest b such that χ_ℓ(G \square Ka,b) = χ_ℓ (G) + a. In this paper we show that the list color function, a list analogue of the chromatic polynomial, provides the right concept and tool for making progress on this problem. Using the list color function, we prove a general improvement on Borowiecki et al.'s 2006 result, and we compute the smallest such b exactly for some large families of chromatic-choosable graphs.