Skip to main content
Added paper title.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

A pretty complete analysis of the chromatic number of random regular graphs can be found here: "On the chromatic number of random regular graphs." Roughly speaking, the chromatic number of a random $d$-regular graph is $k$, where $d \in [(2k-3)\ln(k-1), (2k-2)\ln(k-1)]$.

A pretty complete analysis of the chromatic number of random regular graphs can be found here. Roughly speaking, the chromatic number of a random $d$-regular graph is $k$, where $d \in [(2k-3)\ln(k-1), (2k-2)\ln(k-1)]$.

A pretty complete analysis of the chromatic number of random regular graphs can be found here: "On the chromatic number of random regular graphs." Roughly speaking, the chromatic number of a random $d$-regular graph is $k$, where $d \in [(2k-3)\ln(k-1), (2k-2)\ln(k-1)]$.

Source Link
Alon Amit
  • 6.7k
  • 3
  • 53
  • 83

A pretty complete analysis of the chromatic number of random regular graphs can be found here. Roughly speaking, the chromatic number of a random $d$-regular graph is $k$, where $d \in [(2k-3)\ln(k-1), (2k-2)\ln(k-1)]$.