Random graph coloring: Statistical physics approach

Jort van Mourik; David Saad

doi:10.1103/PhysRevE.66.056120

Random graph coloring: Statistical physics approach

Jort van Mourik^*, David Saad

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-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 language	English
Article number	056120
Number of pages	15
Journal	Physical Review E
Volume	66
Issue number	5
DOIs	https://doi.org/10.1103/PhysRevE.66.056120
Publication status	Published - 21 Nov 2002

Keywords

graph coloring problem
Monte-Carlo simulations
thermodynamics

Access to Document

10.1103/PhysRevE.66.056120

NCRG_2002_009.pdfAccepted author manuscript, 367 KB

Cite this

@article{84a69afcb7a5447e9a8fc1594e480bc0,

title = "Random graph coloring: Statistical physics approach",

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. {\textcopyright}2002 The American Physical Society.",

keywords = "graph coloring problem, Monte-Carlo simulations, thermodynamics",

author = "{van Mourik}, Jort and David Saad",

year = "2002",

month = nov,

day = "21",

doi = "10.1103/PhysRevE.66.056120",

language = "English",

volume = "66",

journal = "Physical Review E",

issn = "1539-3755",

publisher = "American Physical Society",

number = "5",

}

TY - JOUR

T1 - Random graph coloring

T2 - Statistical physics approach

AU - van Mourik, Jort

AU - Saad, David

PY - 2002/11/21

Y1 - 2002/11/21

N2 - 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.

AB - 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.

KW - graph coloring problem

KW - Monte-Carlo simulations

KW - thermodynamics

UR - http://www.scopus.com/inward/record.url?scp=37649027211&partnerID=8YFLogxK

UR - https://journals.aps.org/pre/abstract/10.1103/PhysRevE.66.056120

U2 - 10.1103/PhysRevE.66.056120

DO - 10.1103/PhysRevE.66.056120

M3 - Article

C2 - 12513569

SN - 1539-3755

VL - 66

JO - Physical Review E

JF - Physical Review E

IS - 5

M1 - 056120

ER -

Random graph coloring: Statistical physics approach

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this