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

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

Authors: Sukhada Fadnavis 

Publication date: 12 September 2012

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

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.

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

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

zbMATH Keywords

roots of the chromatic polynomial

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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
• Unimodal, log-concave and Pólya frequency sequences in combinatorics
• Two chromatic polynomial conjectures
• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
• Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree
• On the roots of chromatic polynomials

Cited In (8)

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

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)