162 citations · 853 across the 40 of their papers we have counts for
Showing 2013 · math.COShow all
2 papers · 2 filters
math.CO2013★ 6 cited
On the chromatic number of random regular graphs
Amin Coja-Oghlan, Charilaos Efthymiou, Samuel Hetterich
Let G(n,d) be the random d-regular graph on n vertices. For any integer k exceeding a certain constant k_0 we identify a number d_{k-col} such that G(n,d) is k-colorable w.h.p. if…
math.CO2013
Upper-bounding the k-colorability threshold by counting covers
Amin Coja-Oghlan
Let be the random graph on vertices with edges. Let be its average degree. We prove that fails to be -colorable with high probability if $d>2k…