How Many Colors to Color a Random Graph? Cavity, Complexity, Stability and All That

スポンサーリンク

概要

• 論文の詳細を見る

• We review recent progress on the statiscal physics study of the problem of coloring random graphs with q colors. We discuss the existence of a threshold at connectivity c_q=2qlogq-logq-1+o(1) separting two phases which are respectivily COL (orable) and UNCOL (orable) with q colors; We also argue that the so-called one-step replica symmetry breaking ansatz used to derive these results give exact threshold values, and draw a general phase diagram of the problem.

• 理論物理学刊行会の論文
• 2005-04-30

著者

• Krzakala Florent

  Dipartimento Di Fisica Infm And Smc Universita Di Roma "la Sapienza

関連論文

• Zero Temperature Phase Diagram of Finite Connectivity Spin Glasses
• How Many Colors to Color a Random Graph? Cavity, Complexity, Stability and All That

スポンサーリンク