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

Hemanshu Kaul (Department of Applied Mathematics, Illinois Institute of Technology, Chicago, Il., U.S.A.)

Jeffrey A. Mudrock (Department of Mathematics, College of Lake County, Grayslake, Illinois, U.S.A.)

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