On the Corrádi-Hajnal theorem and a question of Dirac
On the Corrádi-Hajnal theorem and a question of Dirac
复制标题
DOI：
10.1016/j.jctb.2016.05.007
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
H. Kierstead;A. Kostochka;E. Yeager
中科院分区：
文献类型：
--
作者：
H. Kierstead;A. Kostochka;E. Yeager
1963年，Corrádi和Hajnal证明了对所有k≥1和n≥3 k，每个n个顶点上最小度δ(G)≥2 k的图G包含k个不交圈.边界δ(G)≥2k是尖锐的。本文刻画了具有δ(G)≥2 k−1且包含k个不交圈的图。这回答了狄拉克1963年提出的关于不含k个不交圈的(2k−1)-连通图的刻划问题的简单图情形。Enomoto和Wang改进了Corrádi-Hajnal定理，证明了以下Ore型形式：对于所有k≥1和n≥3 k，n个顶点上的每个图G都包含k个不交圈，只要d(X)+d(Y)≥4 k−1对所有不同的不相邻顶点x，y有d(X)+d(Y)≥4 k≥1.我们对k≥3和n−3进一步改进：如果G是n个顶点上的图，使得d(X)+d(Y)4 k Get3对所有不同的不相邻顶点x，y，则G有k个点不交圈当且仅当独立数α(G)≤n−2 k且G不是k=3情形下的两个小例外之一.我们还证明了k=2的情形是由Lovász对没有两个不相交圈的多重图的刻画而来的.
In 1963, Corrádi and Hajnal proved that for all k≥ 1 and n≥ 3 k, every graph G on n vertices with minimum degree δ (G)≥ 2 k contains k disjoint cycles. The bound δ (G)≥ 2 k is sharp. Here we characterize those graphs with δ (G)≥ 2 k− 1 that contain k disjoint cycles. This answers the simple-graph case of Dirac's 1963 question on the characterization of (2 k− 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≥ 1 and n≥ 3 k, every graph G on n vertices contains k disjoint cycles, provided that d (x)+ d (y)≥ 4 k− 1 for all distinct nonadjacent vertices x, y. We refine this further for k≥ 3 and n≥ 3 k+ 1: If G is a graph on n vertices such that d (x)+ d (y)≥ 4 k− 3 for all distinct nonadjacent vertices x, y, then G has k vertex-disjoint cycles if and only if the independence number α (G)≤ n− 2 k and G is not one of two small exceptions in the case k= 3. We also show how the case k= 2 follows from Lovász'characterization of multigraphs with no two disjoint cycles.