Article ID Journal Published Year Pages File Type
5777649 Journal of Combinatorial Theory, Series B 2017 28 Pages PDF
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
, , ,