An improved lower bound of P(G,L)-P(G,k) for k-assignments L

DOI10.1016/J.JCTB.2023.02.002MaRDI QIDQ6038583zbMATH OpenFDO

Authors F. M. Dong, Meiqiao Zhang

Publication date 2 May 2023

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

chromatic polynomiallist-coloringlist-color functionbroken-cycle

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15)

Abstract: Let $G=(V,E)$ be a simple graph with $n$ vertices and $m$ edges, $P(G,k)$ be the chromatic polynomial of $G$, and $P(G,L)$ be the number of $L$-colorings of $G$ for any $k$-assignment $L$. In this article, we show that when $kgem-1ge3$, $P(G,L)-P(G,k)$ is bounded below by $left((k-m+1)k^{n-3}+frac(k-m+3)c3k^{n-5}ight)sumlimit{s}_{uvinE}|L(u)setminusL(v)|$, where $cgefrac(m-1)(m-3)8$, and in particular, if $G$ is $K_3$-free, then $cgem-2choose2+2sqrtm-3$. Consequently, $P(G,L)geP(G,k)$ whenever $kgem-1$.

Recommendations

• Lower bounds and upper bounds for chromatic polynomials
• On upper bounds for real roots of chromatic polynomials
• New bounds for chromatic polynomials and chromatic roots
• On the chromatic polynomial of a graph
• On lower bounds for the chromatic number in terms of vertex degree

Cites work

• scientific article; zbMATH DE number 4091530 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 2199828 (Why is no real title available?)
• An introduction to chromatic polynomials
• Chromatic Polynomials
• Chromatic polynomials
• Lower bounds on the number of triangles in a graph
• 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

(4)

• DP color functions versus chromatic polynomials (II)
• Comparing list-color functions of uniform hypergraphs with their chromatic polynomials. II
• An algebraic approach for counting DP-3-colorings of sparse graphs
• The DP color function of clique-gluings of graphs

This page was built for publication: An improved lower bound of \(P(G,L)-P(G,k)\) for \(k\)-assignments \(L\)

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