Upper-Bounding the $k$-Colorability Threshold by Counting Covers

Electronic Journal Of Combinatorics

Amin Coja-Oghlan¹ 

关键词: Random graphs;    Graph coloring;    Phase transitions;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

Let $G(n,m)$ be the random graph on $n$ vertices with $m$ edges. Let $d=2m/n$ be its average degree. We prove that $G(n,m)$ fails to be $k$-colorable with high probability if $d>2k\ln k-\ln k-1+o_k(1)$. This matches a conjecture put forward on the basi

【 授权许可】

Others