Strengthening Theorems of Dirac and Erdős on Disjoint Cycles |
| |
Authors: | H. A. Kierstead A. V. Kostochka A. McConvey |
| |
Affiliation: | 1. DEPARTMENT OF MATHEMATICS AND STATISTICS, ARIZONA STATE UNIVERSITY, TEMPE, ARIZONA;2. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF ILLINOIS, URBANA, ILLINOIS;3. SOBOLEV INSTITUTE OF MATHEMATICS, NOVOSIBIRSK, RUSSIA;4. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF ILLINOIS, URBANA, ILLINOISContract grant sponsor: NSA;5. Contract grant number: H98230‐12‐1‐0212;6. Contract grant sponsor: NSF;7. Contract grant numbers: DMS‐1266016 and DMS‐1600592;8. Contract grant sponsor: Russian Foundation for Basic Research;9. Contract grant numbers: 15‐01‐05867 and 16‐01‐00499;10. Contract grant sponsor: Campus Research Board, University of Illinois. |
| |
Abstract: | Let be an integer, be the set of vertices of degree at least 2k in a graph G , and be the set of vertices of degree at most in G . In 1963, Dirac and Erd?s proved that G contains k (vertex) disjoint cycles whenever . The main result of this article is that for , every graph G with containing at most t disjoint triangles and with contains k disjoint cycles. This yields that if and , then G contains k disjoint cycles. This generalizes the Corrádi–Hajnal Theorem, which states that every graph G with and contains k disjoint cycles. |
| |
Keywords: | disjoint cycles disjoint triangles minimum degree planar graphs |
|
|