Bounding the list color function threshold from above

DOI10.2140/INVOLVE.2023.16.849MaRDI QIDQ6148301zbMATH OpenOpenAlexFDO

Authors

Publication date 11 January 2024

Published in Involve (Search for Journal in Brave)

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Criticality, the list color function, and list coloring the Cartesian product of graphs
• List coloring and \(n\)-monophilic graphs.
• On the number of list‐colorings
• The chromatic polynomial and list colorings
• When does the list-coloring function of a graph equal its chromatic polynomial

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)