Random graph coloring: Statistical physics approach

Jort van Mourik*, David Saad

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

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
Volume66
Issue number5
DOIs
Publication statusPublished - 21 Nov 2002

Keywords

  • graph coloring problem
  • Monte-Carlo simulations
  • thermodynamics

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

  • Cite this