On the Corrádi-Hajnal theorem and a question of Dirac

详细信息    查看全文

• 作者：H.A. Kierstead^a ; ¹ ; A.V. Kostochka^b ; ^c ; ² ; ^{kostochk@math.uiuc.edu} ; E.C. Yeager^d ; ³ ; ^{Elyse@math.ubc.ca}
• 关键词：Disjoint cycles ; Ore-degree ; Graph packing ; Equitable coloring ; Minimum degree
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：121-148
• 全文大小：660 K
• 卷排序：122

文摘

In 1963, Corrádi and Hajnal proved that for all k≥1k≥1 and n≥3kn≥3k, every graph G on n   vertices with minimum degree δ(G)≥2kδ(G)≥2k contains k   disjoint cycles. The bound δ(G)≥2kδ(G)≥2k is sharp. Here we characterize those graphs with δ(G)≥2k−1δ(G)≥2k−1 that contain k   disjoint cycles. This answers the simple-graph case of Dirac's 1963 question on the characterization of (2k−1)(2k−1)-connected graphs with no k disjoint cycles.Enomoto and Wang refined the Corrádi–Hajnal Theorem, proving the following Ore-type version: For all k≥1k≥1 and n≥3kn≥3k, every graph G on n vertices contains k   disjoint cycles, provided that d(x)+d(y)≥4k−1d(x)+d(y)≥4k−1 for all distinct nonadjacent vertices x,yx,y. We refine this further for k≥3k≥3 and n≥3k+1n≥3k+1: If G is a graph on n   vertices such that d(x)+d(y)≥4k−3d(x)+d(y)≥4k−3 for all distinct nonadjacent vertices x,yx,y, then G has k   vertex-disjoint cycles if and only if the independence number α(G)≤n−2kα(G)≤n−2k and G   is not one of two small exceptions in the case k=3k=3. We also show how the case k=2k=2 follows from Lovász' characterization of multigraphs with no two disjoint cycles.