Random graph coloring: Statistical physics approach

Jort van Mourik*, David Saad

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    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