TY - JOUR

T1 - On directed versions of the Corrádi-Hajnal corollary

AU - Czygrinow, Andrzej

AU - Kierstead, Henry

AU - Molla, Theodore

N1 - Funding Information:
The research of the first author is supported in part by NSA grant H98230-13-1-0211 . The research of the second author is supported in part by NSA grant H98230-12-1-0212 . The research of the third author is supported in part by NSA grant H98230-12-1-0212 .

PY - 2014/11

Y1 - 2014/11

N2 - For k∈N, Corrádi and Hajnal proved that every graph G on 3k vertices with minimum degree δ(G)≥2k has a C3-factor, i.e.,a partitioning of the vertex set so that each part induces the 3-cycle C3. Wang proved that every directed graph G{combining right arrow above} on 3k vertices with minimum total degree δt(G{combining right arrow above}){colon equals}minv∈V(deg-(v)+deg+(v))≥3(3k-1)/2 has a C{combining right arrow above}3-factor, where C{combining right arrow above}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≥1 and b≥0 with a+b=k, every directed graph G{combining right arrow above} on 3k vertices with minimum total degree δt(G{combining right arrow above})≥4k-1 has a factor consisting of a copies of T{combining right arrow above}3 and b copies of C{combining right arrow above}3, where T{combining right arrow above}3 is the transitive tournament on three vertices. In particular, using b=0, there is a T{combining right arrow above}3-factor of G{combining right arrow above}, and using a=1, it is possible to obtain a C{combining right arrow above}3-factor of G{combining right arrow above} by reversing just one edge of G{combining right arrow above}. All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph G{combining right arrow above} on 3. k vertices with minimum semidegree δ0(G{combining right arrow above}){colon equals}minv∈Vmin(deg-(v),deg+(v))≥2k has a C{combining right arrow above}3-factor, and prove that this is asymptotically correct.

AB - For k∈N, Corrádi and Hajnal proved that every graph G on 3k vertices with minimum degree δ(G)≥2k has a C3-factor, i.e.,a partitioning of the vertex set so that each part induces the 3-cycle C3. Wang proved that every directed graph G{combining right arrow above} on 3k vertices with minimum total degree δt(G{combining right arrow above}){colon equals}minv∈V(deg-(v)+deg+(v))≥3(3k-1)/2 has a C{combining right arrow above}3-factor, where C{combining right arrow above}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≥1 and b≥0 with a+b=k, every directed graph G{combining right arrow above} on 3k vertices with minimum total degree δt(G{combining right arrow above})≥4k-1 has a factor consisting of a copies of T{combining right arrow above}3 and b copies of C{combining right arrow above}3, where T{combining right arrow above}3 is the transitive tournament on three vertices. In particular, using b=0, there is a T{combining right arrow above}3-factor of G{combining right arrow above}, and using a=1, it is possible to obtain a C{combining right arrow above}3-factor of G{combining right arrow above} by reversing just one edge of G{combining right arrow above}. All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph G{combining right arrow above} on 3. k vertices with minimum semidegree δ0(G{combining right arrow above}){colon equals}minv∈Vmin(deg-(v),deg+(v))≥2k has a C{combining right arrow above}3-factor, and prove that this is asymptotically correct.

UR - http://www.scopus.com/inward/record.url?scp=84902173419&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902173419&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2014.05.006

DO - 10.1016/j.ejc.2014.05.006

M3 - Article

AN - SCOPUS:84902173419

SN - 0195-6698

VL - 42

SP - 1

EP - 14

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -