Bounding the list color function threshold from above

DOI10.2140/INVOLVE.2023.16.849zbMATH Open1530.05046arXiv2207.04831OpenAlexW4389660651MaRDI QIDQ6148301FDOQ6148301

Authors:

Publication date: 11 January 2024

Published in: Involve (Search for Journal in Brave)

Abstract: The chromatic polynomial of a graph $G$, denoted $P(G,m)$, is equal to the number of proper $m$-colorings of $G$ for each $minmathbbN$. In 1990, Kostochka and Sidorenko introduced the list color function of graph $G$, denoted $P_{ell}(G,m)$, which is a list analogue of the chromatic polynomial. The list color function threshold of $G$, denoted $au(G)$, is the smallest $kgeqchi(G)$ such that $P_{ell}(G,m)=P(G,m)$ whenever $mgeqk$. It is known that for every graph $G$, $au(G)$ is finite, and in fact, $au(G)leq(|E(G)|-1)/ln(1+sqrt2)+1$. It is also known that when $G$ is a cycle or chordal graph, $G$ is enumeratively chromatic-choosable which means $au(G)=chi(G)$. A recent paper of Kaul et al. suggests that understanding the list color function threshold of complete bipartite graphs is essential to the study of the extremal behavior of $au$. In this paper we show that for any $ngeq2$, $au(K_{2,n})leqlceil(n+2.05)/1.24ceil$ which gives an improvement on the general upper bound for $au(G)$ when $G=K_{2,n}$. We also develop additional tools that allow us to show that $au(K_{2,3})=chi(K_{2,3})$ and $au(K_{2,4})=au(K_{2,5})=3$.

Full work available at URL: https://arxiv.org/abs/2207.04831

Recommendations

• On the list color function threshold
• When does the list-coloring function of a graph equal its chromatic polynomial
• List coloring a Cartesian product with a complete bipartite factor
• On the chromatic polynomial and counting DP-colorings of graphs
• The list-coloring function of signed graphs

zbMATH Keywords

list coloringchromatic polynomiallist color functionenumerative chromatic-choosabilitylist color function threshold

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The chromatic polynomial and list colorings
• When does the list-coloring function of a graph equal its chromatic polynomial
• On the number of list‐colorings
• Criticality, the list color function, and list coloring the Cartesian product of graphs
• List coloring and \(n\)-monophilic graphs.

Cited In (1)

• On the list color function threshold

This page was built for publication: Bounding the list color function threshold from above

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148301)