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

[摘要] 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

[学科分类] 离散数学和组合数学

[关键词] Random graphs;Graph coloring;Phase transitions