Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree

DOI10.1017/S0963548307008632MaRDI QIDQ3512601zbMATH OpenFDO

Authors Aldo Procacci, Roberto Fernandez

Publication date 21 July 2008

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

chromatic polynomialtriangle free verticeszero free

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We prove that the chromatic polynomial $P_{m}athbbG(q)$ of a finite graph $mathbbG$ of maximal degree $D$ is free of zeros for $cardqge{C}^{\ast }(D)$ with ${\displaystyle }$ C^*(D) = min_{0<x<2^{1over D}-1} {(1+x)^{D-1}over x [2-(1+x)^D]} ${\displaystyle }$ This improves results by Sokal (2001) and Borgs (2005). Furthermore, we present a strengthening of this condition for graphs with no triangle-free vertices.

Recommendations

• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
• Bounds For The Real Zeros of Chromatic Polynomials
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• A zero-free interval for chromatic polynomials
• On the location of chromatic zeros of series-parallel graphs

Cites work

• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
• Cluster expansion for abstract polymer models
• Polymer gas approach to \(N\)-body lattice systems
• Potts model on infinite graphs and the limit of chromatic polynomials

Cited in

(29)

• A note on the shameful conjecture
• Cayley trees do not determine the maximal zero-free locus of the independence polynomial
• On a conjecture of Sokal concerning roots of the independence polynomial
• New bounds for chromatic polynomials and chromatic roots
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• Chromatic polynomials
• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
• Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
• Chromatic polynomials of random graphs
• Continuous particles in the canonical ensemble as an abstract polymer gas
• Bounds For The Real Zeros of Chromatic Polynomials
• Improved bounds on coloring of graphs
• On Brenti's conjecture about the log-concavity of the chromatic polynomial
• On Lennard-Jones type potentials and hard-core potentials with an attractive tail
• Virial series for a system of classical particles interacting through a pair potential with negative minimum
• Sidorenko's conjecture, colorings and independent sets
• Approximating the chromatic polynomial is as hard as computing it exactly
• On the location of chromatic zeros of series-parallel graphs
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with extra-vertex boundary conditions
• Improved bounds for the zeros of the chromatic polynomial via Whitney's broken circuit theorem
• On the zeroes of hypergraph independence polynomials
• Central limit theorems and the geometry of polynomials
• Deterministic approximate counting of colorings with fewer than 2 colors via absence of zeros
• On the zero-free region for the chromatic polynomial of graphs with maximum degree and girth g
• Correlation decay and partition function zeros: algorithms and phase transitions
• A remark on the Whitney broken circuit theorem
• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
• A little statistical mechanics for the graph theorist
• On the convergence of cluster expansions for polymer gases

This page was built for publication: Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree

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