Contents Online
Journal of Combinatorics
Volume 12 (2021)
Number 3
Criticality, the list color function, and list coloring the cartesian product of graphs
Pages: 479 – 514
DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n3.a4
Authors
Abstract
We initiate the study of a notion of color-criticality in the context of chromatic-choosability. We define graph $G$ to be strong $k$-chromatic-choosable if $\chi(G) = k$ and every $(k-1)$-assignment for which $G$ is not list-colorable has the property that the lists are the same for all vertices. That is the usual coloring is, in some sense, the obstacle to list-coloring. We prove basic properties of strongly chromatic-choosable graphs such as vertex-criticality, and we construct infinite families of strongly chromatic-choosable graphs. We derive a sufficient condition for the existence of at least two list colorings of strongly chromatic-choosable graphs and use it to show that: if $M$ is a strong $k$-chromatic-choosable graph with $\lvert E(M) \rvert \leq \lvert V (M) \rvert (k-2)$ and $H$ is a graph that contains a Hamilton path, $w_1, w_2, \dotsc , w_m$, such that $w_i$ has at most $\rho \geq 1$ neighbors among $w_1, \dotsc , w_{i-1}$, then $\chi_\ell (M \Box H) \leq k + \rho - 1$. We show that this bound is sharp for all $\rho \geq 1$ by generalizing the theorem to apply to $H$ that are $(M,\rho)$-Cartesian accommodating which is a notion we define with the help of the list color function, $P_\ell (G, k)$, the list analogue of the chromatic polynomial.
We also use the list color function to determine the list chromatic number of certain star-like graphs: $\chi_\ell (M \Box K_{1,s}) = k$ if $s \lt P_\ell (M,k)$, and $k + 1$ if $s \geq P_\ell (M,k)$, where $M$ is a strong $k$-chromatic-choosable graph. We use the fact that $P_\ell (M,k)$ equals $P(M,k)$, the chromatic polynomial, when $M$ is an odd cycle, complete graph, or the join of an odd cycle with a complete graph to prove $\chi_\ell (C_{2l+1} \Box K_{1,s})$ transitions from $3$ to $4$ at $s = 2^{2l+1} - 2, \chi_\ell (K_n \Box K_{1,s})$ transitions from $n$ to $n + 1$ at $s = n!$, and $\chi_\ell ((K_n \vee C_{2l+1}) \Box K_{1,s})$ transitions from $n+3$ to $n+4$ at $s = \frac{1}{3} (n+3)!(4^l -1)$.
Keywords
Cartesian product of graphs, list coloring, criticality, list color function
2010 Mathematics Subject Classification
05C15
Received 15 September 2018
Accepted 11 September 2020
Published 8 November 2021