Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Coloring random graphs.

R Mulet1, A Pagnani, M Weigt

  • 1International Centre for Theoretical Physics, Strada Costiera 11, P.O. Box 586, 34100 Trieste, Italy.

Physical Review Letters
|December 18, 2002
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Evolutionary emergent metabolic interactions in cell cultures: A statistical mechanics point of view.

Physical review. E·2025
Same author

Author Correction: Understanding epistatic networks in the B1 β-lactamases through coevolutionary statistical modeling and deep mutational scanning.

Nature communications·2024
Same author

Understanding epistatic networks in the B1 β-lactamases through coevolutionary statistical modeling and deep mutational scanning.

Nature communications·2024
Same author

Structure of the space of folding protein sequences defined by large language models.

Physical biology·2024
Same author

Native state of natural proteins optimizes local entropy.

Physical review. E·2022
Same author

From random point processes to hierarchical cavity master equations for stochastic dynamics of disordered systems in random graphs: Ising models and epidemics.

Physical review. E·2021
Same journal

Erratum: Bacterial Turbulence at Compressible Fluid Interfaces [Phys. Rev. Lett. 136, 138301 (2026)].

Physical review letters·2026
Same journal

Unveiling Light-Quark Yukawa Flavor Structure via Dihadron Fragmentation at Lepton Colliders.

Physical review letters·2026
Same journal

Adaptable Route to Fast Coherent State Transport via Bang-Bang-Bang Protocols.

Physical review letters·2026
Same journal

Topological Transition and Emergence of Elasticity of Dislocation in Skyrmion Lattice: Beyond Kittel's Magnetic-Polar Analogy.

Physical review letters·2026
Same journal

Pound-Drever-Hall Method for Superconducting-Qubit Readout.

Physical review letters·2026
Same journal

Coupling a ^{73}Ge Nuclear Spin to an Electrostatically Defined Quantum Dot in Silicon.

Physical review letters·2026
See all related articles

This study on graph coloring reveals a critical connectivity threshold. Below this point, graphs are colorable; above it, they become uncolorable, revealing complexity in local search algorithms.

Area of Science:

  • Graph theory
  • Computational complexity
  • Statistical physics

Background:

  • The graph coloring problem is a fundamental problem in computer science and mathematics.
  • Understanding the behavior of graph coloring on random graphs is crucial for theoretical and practical applications.

Purpose of the Study:

  • To investigate the solvability of the graph coloring problem on random graphs with finite average connectivity.
  • To determine the critical average connectivity threshold for colorability as a function of the number of available colors.

Main Methods:

  • Analysis of random graphs with finite average connectivity.
  • Identification of critical average connectivity values (c(q)).
  • Characterization of a clustering phase below the critical threshold.

Related Experiment Videos

Main Results:

  • Graphs with low average connectivity are almost always properly colorable.
  • Graphs with high average connectivity are uncolorable.
  • A precise critical average connectivity c(q) is determined for a given number of colors q.
  • A clustering phase exists below c(q) with an exponential number of ground states.

Conclusions:

  • The study establishes a sharp threshold for graph colorability based on average connectivity.
  • The identified clustering phase and metastable states explain the complexity observed in local search algorithms for graph coloring.