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

DOI10.1016/J.JCTB.2023.02.002zbMATH Open1512.05137arXiv2206.14536MaRDI QIDQ6038583FDOQ6038583

Authors: F. M. Dong, Meiqiao Zhang 

Publication date: 2 May 2023

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

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

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

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

zbMATH Keywords

chromatic polynomiallist-coloringlist-color functionbroken-cycle

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An introduction to chromatic polynomials
• Lower bounds on the number of triangles in a graph
• 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
• Chromatic Polynomials
• Title not available (Why is that?)
• Chromatic polynomials

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)