(k+1)-Cores Have k-Factors

作者：Chan Siu On^*; Molloy Michael

来源：Combinatorics Probability & Computing, 2012, 21(6): 882-896.

DOI：10.1017/S096354831200034X

We prove that the threshold for the appearance of a k-regular subgraph in Gn,p is at most the threshold for the appearance of a non-empty (k + 1)-core. This improves a result of Pralat, Verstraete and Wormald [5] and proves a conjecture of Bollobas, Kim and Verstraete [3].

• 出版日期2012-11