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

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

Other MSP Journals

This article is available for purchase or by subscription. See below.

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.

PDF Access Denied

We have not been able to recognize your IP address 18.219.103.183 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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