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