On the phase transitions of graph coloring and independent sets

Valmir C. Barbosa and Rubens G. Ferreira

Physica A: Statistical Mechanics and its Applications, 2004, vol. 343, issue C, 401-423

Abstract: We study combinatorial indicators related to the characteristic phase transitions associated with the optimization problems of coloring the nodes of a graph with the minimum number of colors and of finding an independent set of maximum cardinality in a graph. In particular, we investigate the role of the acyclic orientations of the graph in the hardness of finding the graph's chromatic number and independence number. We provide empirical evidence that, along a sequence of increasingly denser random graphs, the fraction of acyclic orientations that are “shortest” peaks when the chromatic number increases, and that such maxima tend to coincide with locally easiest instances of the problem. Similar evidence is provided concerning the “widest” acyclic orientations and the independence number.

Keywords: Graph coloring; Maximum independent sets; Phase transitions; Acyclic orientations (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437104007344
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:343:y:2004:i:c:p:401-423

DOI: 10.1016/j.physa.2004.05.055

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().