Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777649 | Journal of Combinatorial Theory, Series B | 2017 | 28 Pages |
Abstract
Enomoto and Wang refined the Corrádi-Hajnal Theorem, proving the following Ore-type version: For all kâ¥1 and nâ¥3k, every graph G on n vertices contains k disjoint cycles, provided that d(x)+d(y)â¥4kâ1 for all distinct nonadjacent vertices x,y. We refine this further for kâ¥3 and nâ¥3k+1: If G is a graph on n vertices such that d(x)+d(y)â¥4kâ3 for all distinct nonadjacent vertices x,y, then G has k vertex-disjoint cycles if and only if the independence number α(G)â¤nâ2k 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
H.A. Kierstead, A.V. Kostochka, E.C. Yeager,