TY - JOUR

T1 - Sharpening an Ore-type version of the Corrádi–Hajnal theorem

AU - Kierstead, Henry

AU - Kostochka, A. V.

AU - Molla, T.

AU - Yeager, E. C.

N1 - Funding Information:
Research of H. A. Kierstead is supported in part by NSA Grant H98230-12-1-0212. Research of A. V. Kostochka is supported in part by NSF Grants DMS-1266016 and DMS-1600592 and by Grant NSh.1939.2014.1 of the President of Russia for Leading Scientific Schools. Research of T. Molla is supported in part by NSF Grant DMS-1500121. Research of E. C. Yeager is supported in part by NSF Grants DMS 08-38434 and DMS-1266016.
Publisher Copyright:
© 2016, The Author(s).

PY - 2017/10/1

Y1 - 2017/10/1

N2 - Corrádi and Hajnal (Acta Math Acad Sci Hung 14:423–439, 1963) proved that for all k≥ 1 and n≥ 3 k, every (simple) graph G on n vertices with minimum degree δ(G) ≥ 2 k contains k disjoint cycles. The degree bound is sharp. Enomoto and Wang proved the following Ore-type refinement of the Corrádi–Hajnal theorem: 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. Very recently, it was refined 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. But the most difficult case, n= 3 k, was not handled. In this case, there are more exceptional graphs, the statement is more sophisticated, and some of the proofs do not work. In this paper we resolve this difficult case and obtain the full picture of extremal graphs for the Ore-type version of the Corrádi–Hajnal theorem. Since any k disjoint cycles in a 3k-vertex graph G must be 3-cycles, the existence of such k cycles is equivalent to the existence of an equitable k-coloring of the complement of G. Our proof uses the language of equitable colorings, and our result can be also considered as an Ore-type version of a partial case of the Chen–Lih–Wu Conjecture on equitable colorings.

AB - Corrádi and Hajnal (Acta Math Acad Sci Hung 14:423–439, 1963) proved that for all k≥ 1 and n≥ 3 k, every (simple) graph G on n vertices with minimum degree δ(G) ≥ 2 k contains k disjoint cycles. The degree bound is sharp. Enomoto and Wang proved the following Ore-type refinement of the Corrádi–Hajnal theorem: 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. Very recently, it was refined 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. But the most difficult case, n= 3 k, was not handled. In this case, there are more exceptional graphs, the statement is more sophisticated, and some of the proofs do not work. In this paper we resolve this difficult case and obtain the full picture of extremal graphs for the Ore-type version of the Corrádi–Hajnal theorem. Since any k disjoint cycles in a 3k-vertex graph G must be 3-cycles, the existence of such k cycles is equivalent to the existence of an equitable k-coloring of the complement of G. Our proof uses the language of equitable colorings, and our result can be also considered as an Ore-type version of a partial case of the Chen–Lih–Wu Conjecture on equitable colorings.

KW - Disjoint cycles

KW - Equitable coloring

KW - Minimum degree

UR - http://www.scopus.com/inward/record.url?scp=85006851580&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85006851580&partnerID=8YFLogxK

U2 - 10.1007/s12188-016-0168-8

DO - 10.1007/s12188-016-0168-8

M3 - Article

AN - SCOPUS:85006851580

SN - 0025-5858

VL - 87

SP - 299

EP - 335

JO - Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg

JF - Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg

IS - 2

ER -