On Brenti's conjecture about the log-concavity of the chromatic polynomial

DOI10.1016/J.EJC.2012.05.001zbMATH Open1248.05088OpenAlexW2002401386WikidataQ122912691 ScholiaQ122912691MaRDI QIDQ449211FDOQ449211

Authors Sukhada Fadnavis

Publication date 12 September 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

roots of the chromatic polynomial

Mathematics Subject Classification ID

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

Abstract: The chromatic polynomial is a well studied object in graph theory. There are many results and conjectures about the log-concavity of the chromatic polynomial and other polynomials related to it. The location of the roots of these polynomials has also been well studied. One famous result due to A. Sokal and C. Borgs provides a bound on the absolute value of the roots of the chromatic polynomial in terms of the highest degree of the graph. We use this result to prove a modification of a log-concavity conjecture due to F. Brenti. The original conjecture of Brenti was that the chromatic polynomial is log-concave on the natural numbers. This was disproved by Paul Seymour by presenting a counter example. We show that the chromatic polynomial $P_G(q)$ of graph $G$ is in fact log-concave for all $q>CDelta+1$ for an explicit constant $C<10$, where $Delta$ denotes the highest degree of $G$. We also provide an example which shows that the result is not true for constants $C$ smaller than 1.

Recommendations

• Two chromatic polynomial conjectures
• Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials
• scientific article; zbMATH DE number 3869357
• Publication:4508372
• Proof of a chromatic polynomial conjecture

Cites work

• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• Expansions of Chromatic Polynomials and Log-Concavity
• Location of Zeros of Chromatic and Related Polynomials of Graphs
• On the roots of chromatic polynomials
• Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree
• Two chromatic polynomial conjectures
• Unimodal, log-concave and Pólya frequency sequences in combinatorics

Cited in

(8)

• scientific article; zbMATH DE number 3869357 (Why is no real title available?)
• Log-concavity and log-convexity of moments of averages of i.i.d. random variables
• A note on the shameful conjecture
• Expansions of Chromatic Polynomials and Log-Concavity
• Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials
• Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
• Enumeration of graded (3+1)-avoiding posets
• Chromatic polynomials of simplicial complexes

This page was built for publication: On Brenti's conjecture about the log-concavity of the chromatic polynomial

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