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

Abstract: In 1963, Corr'adi and Hajnal proved that for all

k g e q 1

and

n g e q 3 k

, every graph

G

on

n

vertices with minimum degree

d e l t a (G) g e q 2 k

contains

k

disjoint cycles. The bound

d e l t a (G) g e q 2 k

is sharp. Here we characterize those graphs with

d e l t a (G) g e q 2 k - 1

that contain

k

disjoint cycles. This answers the simple-graph case of Dirac's 1963 question on the characterization of

(2 k - 1)

-connected graphs with no

k

disjoint cycles. Enomoto and Wang refined the Corr'adi-Hajnal Theorem, proving the following Ore-type version: For all

k g e q 1

and

n g e q 3 k

, every graph

G

on

n

vertices contains

k

disjoint cycles, provided that

d (x) + d (y) g e q 4 k - 1

for all distinct nonadjacent vertices

x, y

. We refine this further for

k g e q 3

and

n g e q 3 k + 1

: If

G

is a graph on

n

vertices such that

d (x) + d (y) g e q 4 k - 3

for all distinct nonadjacent vertices

x, y

, then

G

has

k

vertex-disjoint cycles if and only if the independence number

a l p h a (G) l e q n - 2 k

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'asz' characterization of multigraphs with no two disjoint cycles.

Recommendations

Cites Work

Cited In (13)

This page was built for publication: On the Corrádi-Hajnal theorem and a question of Dirac