Name
Abstract | ||
|---|---|---|
In 1963, Corrádi and Hajnal proved that for all k≥1 and n≥3k, every graph G on n vertices with minimum degree δ(G)≥2k contains k disjoint cycles. The bound δ(G)≥2k is sharp. Here we characterize those graphs with δ(G)≥2k−1 that contain k disjoint cycles. This answers the simple-graph case of Dirac's 1963 question on the characterization of (2k−1)-connected graphs with no k disjoint cycles. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.jctb.2016.05.007 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
Disjoint cycles,Ore-degree,Graph packing,Equitable coloring,Minimum degree | Discrete mathematics,Graph,Independence number,Combinatorics,Disjoint sets,Vertex (geometry),Graph packing,Dirac (video compression format),Mathematics,Equitable coloring | Journal |
Volume | ISSN | Citations |
122 | 0095-8956 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henry A Kierstead | 1 | 132 | 18.28 |
| Alexandr V. Kostochka | 2 | 682 | 89.87 |
| Elyse Yeager | 3 | 6 | 2.25 |