科研之友
微信
新浪微博
Facebook
分享链接
摘要
Corradi and Hajnal proved that for every k a parts per thousand yen 1 and n a parts per thousand yen 3k, every n-vertex graph with minimum degree at least 2k contains k vertex-disjoint cycles. This implies that every 3k-vertex graph with maximum degree at most k - 1 has an equitable k-coloring. We prove that for sa{3,4} if an sk-vertex graph G with maximum degree at most k has no equitable k-coloring, then G either contains K (k+1) or k is odd and G contains K (k,k) . This refines the above corollary of the Corradi-Hajnal Theorem and also is a step toward the conjecture by Chen, Lih, and Wu that for r a parts per thousand yen 3, the only connected graphs with maximum degree at most r that are not equitably r-colorable are K (r,r) (for odd r) and K (r+1).
- 出版日期2015-8
