English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Chromatic polynomials of random graphs

MPS-Authors
/persons/resource/persons173698

van Bussel,  Frank
Max Planck Research Group Network Dynamics, Max Planck Institute for Dynamics and Self-Organization, Max Planck Society;

/persons/resource/persons173510

Fliegner,  Denny
Department of Nonlinear Dynamics, Max Planck Institute for Dynamics and Self-Organization, Max Planck Society;

/persons/resource/persons173689

Timme,  Marc
Max Planck Research Group Network Dynamics, Max Planck Institute for Dynamics and Self-Organization, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

van Bussel, F., Ehrlich, C., Fliegner, D., Stolzenberg, S., & Timme, M. (2010). Chromatic polynomials of random graphs. Journal of Physics A: Mathematical and Theoretical, 43: 175002. doi:10.1088/1751-8113/43/17/175002.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0029-1279-B
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.