Chromatic polynomials of random graphs

DOI10.1088/1751-8113/43/17/175002zbMATH Open1190.82026arXiv1709.06209OpenAlexW3101414017WikidataQ56267069 ScholiaQ56267069MaRDI QIDQ3560985FDOQ3560985

Marc Timme, Denny Fliegner, Frank Van Bussel, Christoph Ehrlich, Sebastian Stolzenberg

Publication date: 17 May 2010

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Abstract: Chromatic polynomials and related graph invariants are central objects in both graph theory and statistical physics. Computational difficulties, however, have so far restricted studies of such polynomials to graphs that were either very small, very sparse or highly structured. Recent algorithmic advances (Timme et al 2009 New J. Phys. 11 023001) now make it possible to compute chromatic polynomials for moderately sized graphs of arbitrary structure and number of edges. Here we present chromatic polynomials of ensembles of random graphs with up to 30 vertices, over the entire range of edge density. We specifically focus on the locations of the zeros of the polynomial in the complex plane. The results indicate that the chromatic zeros of random graphs have a very consistent layout. In particular, the crossing point, the point at which the chromatic zeros with non-zero imaginary part approach the real axis, scales linearly with the average degree over most of the density range. While the scaling laws obtained are purely empirical, if they continue to hold in general there are significant implications: the crossing points of chromatic zeros in the thermodynamic limit separate systems with zero ground state entropy from systems with positive ground state entropy, the latter an exception to the third law of thermodynamics.

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

Recommendations

• The structure of chromatic polynomials of planar triangulations and implications for chromatic zeros and asymptotic limiting quantities
• scientific article; zbMATH DE number 867660
• scientific article; zbMATH DE number 205347
• Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree
• Location of Zeros of Chromatic and Related Polynomials of Graphs

zbMATH Keywords

graph algorithmsrandom graphschromatic polynomialsdynamic lattice systems

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph polynomials (05C31) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Cited In (4)

• Chromatic polynomials and network reliability
• Characteristic power series of graph limits
• On the absolute sum of chromatic polynomial coefficient of graphs
• Random reals and polarized colorings

This page was built for publication: Chromatic polynomials of random graphs

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