Random graph coloring: Statistical physics approach

Jort van Mourik*, David Saad

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


The problem of vertex coloring in random graphs is studied using methods of statistical physics and probability. Our analytical results are compared to those obtained by exact enumeration and Monte Carlo simulations. We critically discuss the merits and shortcomings of the various methods, and interpret the results obtained. We present an exact analytical expression for the two-coloring problem as well as general replica symmetric approximated solutions for the thermodynamics of the graph coloring problem with p colors and K-body edges. ©2002 The American Physical Society.

Original languageEnglish
Article number056120
Number of pages15
JournalPhysical Review E
Issue number5
Publication statusPublished - 21 Nov 2002


  • graph coloring problem
  • Monte-Carlo simulations
  • thermodynamics


Dive into the research topics of 'Random graph coloring: Statistical physics approach'. Together they form a unique fingerprint.

Cite this