On directed versions of the Corrádi-Hajnal corollary

Abstract: For

k i n m a t h b b N

, Corr'adi and Hajnal proved that every graph

G

on

3 k

vertices with minimum degree

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

has a

C_{3}

-factor, i.e., a partitioning of the vertex set so that each part induces the 3-cycle

C_{3}

. Wang proved that every directed graph

o v e r r i g h t a r r o w G

on

3 k

vertices with minimum total degree

d e l t a_{t} (o v e r r i g h t a r r o w G) := m i n_{v i n V} (d e g^{-} (v) + d e g^{+} (v)) g e 3 (3 k - 1) / 2

has a

o v e r r i g h t a r r o w C_{3}

-factor, where

o v e r r i g h t a r r o w C_{3}

is the directed 3-cycle. The degree bound in Wang's result is tight. However, our main result implies that for all integers

a g e 1

and

b g e 0

with

a + b = k

, every directed graph

o v e r r i g h t a r r o w G

on

3 k

vertices with minimum total degree

d e l t a_{t} (o v e r r i g h t a r r o w G) g e 4 k - 1

has a factor consisting of

a

copies of

o v e r r i g h t a r r o w T_{3}

and

b

copies of

o v e r r i g h t a r r o w C_{3}

, where

o v e r r i g h t a r r o w T_{3}

is the transitive tournament on three vertices. In particular, using

b = 0

, there is a

o v e r r i g h t a r r o w T_{3}

-factor of

o v e r r i g h t a r r o w G

, and using

a = 1

, it is possible to obtain a

o v e r r i g h t a r r o w C_{3}

-factor of

o v e r r i g h t a r r o w G

by reversing just one edge of

o v e r r i g h t a r r o w G

. All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph

o v e r r i g h t a r r o w G

on

3 k

vertices with minimum semidegree

d e l t a_{0} (o v e r r i g h t a r r o w G) := m i n_{v i n V} m i n (d e g^{-} (v), d e g^{+} (v)) g e 2 k

has a

o v e r r i g h t a r r o w C_{3}

-factor, and prove that this is asymptotically correct.

Recommendations

Cites Work

Cited In (13)

This page was built for publication: On directed versions of the Corrádi-Hajnal corollary