Source author record

E. C. Yeager

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On the Corrádi-Hajnal Theorem and a question of Dirac

In 1963, Corrádi and Hajnal proved that for all $k\geq1$ and $n\geq3k$ , every graph $G$ on $n$ vertices with minimum degree $δ(G)\geq2k$ contains $k$ disjoint cycles. The bound $δ(G) \geq 2k$ is sharp. Here we characterize those graphs with $δ(G)\geq2k-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. Enomoto and Wang refined the Corrádi-Hajnal Theorem, proving the following Ore-type version: For all $k\geq1$ and $n\geq3k$ , every graph $G$ on $n$ vertices contains $k$ disjoint cycles, provided that $d(x)+d(y)\geq 4k-1$ for all distinct nonadjacent vertices $x,y$ . We refine this further for $k\geq3$ and $n\geq3k+1$ : If $G$ is a graph on $n$ vertices such that $d(x)+d(y)\geq 4k-3$ for all distinct nonadjacent vertices $x,y$ , then $G$ has $k$ vertex-disjoint cycles if and only if the independence number $α(G)\leq 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.

preprint2015arXiv

The (2k-1)-connected multigraphs with at most k-1 disjoint cycles

In 1963, Corrádi and Hajnal proved that for all $k \ge 1$ and $n \ge 3k$ , every (simple) graph on n vertices with minimum degree at least 2k contains k disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2k-1)-connected multigraphs do not contain k disjoint cycles? Recently, the authors characterized the simple graphs G with minimum degree $δ(G) \ge 2k-1$ that do not contain k disjoint cycles. We use this result to answer Dirac's question in full.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.