Random Graph Coloring - a Statistical Physics Approach
arXiv:cond-mat/0207453 · doi:10.1103/PhysRevE.66.056120
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 2-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.
arXiv comment17 pages, 9 figures
References in corpus (10)
- Optimization with Extremal Dynamics
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Statistical mechanics of the random K-SAT model
- Typical Performance of Gallager-type Error-Correcting Codes
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- The Statistical Physics of Regular Low-Density Parity-Check Error-Correcting Codes
- Weight Space Structure and Internal Representations: a Direct Approach to Learning and Generalization in Multilayer Neural Network
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Phase coexistence and finite-size scaling in random combinatorial problems
- Cryptographical Properties of Ising Spin Systems
Cited by in corpus (23)
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Phase Transitions in the Coloring of Random Graphs
- A Landscape Analysis of Constraint Satisfaction Problems
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Polynomial iterative algorithms for coloring and analyzing random graphs
- On the freezing of variables in random constraint satisfaction problems
- Generalization of the cavity method for adiabatic evolution of Gibbs states
- Networking - A Statistical Physics Perspective
- Potts Glass on Random Graphs
- Statistical Physics of Hard Optimization Problems
- Finitely coordinated models for low-temperature phases of amorphous systems
- Bicoloring Random Hypergraphs
- The cavity method for large deviations
- Statistical physics of hard combinatorial optimization: The vertex cover problem
- Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
- Antiferromagnetic Potts model on the Erdos-Renyi random graph
- Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
- Minimizing Unsatisfaction in Colourful Neighbourhoods
- Typical kernel size and number of sparse random matrices over GF(q) - a statistical physics approach
- Colouring random graphs and maximising local diversity
- The effect of quantum fluctuations on the coloring of random graphs
- Replication-based Inference Algorithms for Hard Computational Problems
- Academic Meeting Scheduling Using an Antiferromagnetic Potts Model