Bounding the list color function threshold from above

Kaul, Hemanshu; Kumar, Akash; Liu, Andrew; Mudrock, Jeffrey A.; Rewers, Patrick; Shin, Paul; Tanahara, Michael Scott; To, Khue

doi:10.2140/involve.2023.16.849

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Bounding the list color function threshold from above

Hemanshu Kaul, Akash Kumar, Andrew Liu, Jeffrey A. Mudrock, Patrick Rewers, Paul Shin, Michael Scott Tanahara and Khue To

Vol. 16 (2023), No. 5, 849–882

DOI: 10.2140/involve.2023.16.849

Abstract

The chromatic polynomial of a graph $G$ , denoted by $P (G, m)$ , is equal to the number of proper $m$ -colorings of $G$ for each $m \in ℕ$ . In 1990, Kostochka and Sidorenko introduced the list color function of graph $G$ , denoted by $P_{ℓ} (G, m)$ , which is a list analogue of the chromatic polynomial. The list color function threshold of $G$ , denoted by $τ (G)$ , is the smallest $k$ such that $P (G, k) > 0$ and $P_{ℓ} (G, m) = P (G, m)$ whenever $m \geq k$ . It is known that for every graph $G$ , $τ (G)$ is finite, and a recent paper of Kaul et al. suggests that complete bipartite graphs may be the key to understanding the extremal behavior of $τ$ . We develop tools for bounding the list color function threshold of complete bipartite graphs from above. We show that, for any $n \geq 2$ , $τ (K_{2, n}) \leq ⌈ (n + 2.05) ∕ 1.24 ⌉$ . Interestingly, our proof makes use of classical results such as Rolle’s theorem and Descartes’ rule of signs.

Keywords

list coloring, chromatic polynomial, list color function, list color function threshold, enumerative chromatic-choosability

Mathematical Subject Classification

Primary: 05C15, 05C30

Supplementary material

Python code

Milestones

Received: 17 July 2022

Revised: 5 November 2022

Accepted: 9 November 2022

Published: 9 December 2023

Communicated by Ronald Gould

Authors

Hemanshu Kaul
Department of Applied Mathematics Illinois Institute of Technology Chicago, IL United States

Akash Kumar
Department of Mathematics College of Lake County Grayslake, IL United States

Andrew Liu
Department of Mathematics College of Lake County Grayslake, IL United States

Jeffrey A. Mudrock
Department of Mathematics College of Lake County Grayslake, IL United States

Patrick Rewers
Department of Mathematics College of Lake County Grayslake, IL United States

Paul Shin
Department of Mathematics College of Lake County Grayslake, IL United States

Michael Scott Tanahara
Department of Mathematics College of Lake County Grayslake, IL United States

Khue To
Department of Mathematics College of Lake County Grayslake, IL United States

Vol. 16, No. 5, 2023