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 |
|
|
