2013/09/18 by Czygrinow, Andrzej, Kierstead, H. A., Molla, Theodore
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1309.4520
For k ∈ \mathbb 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 \overrightarrow G on 3k vertices with minimum total degree δt(\overrightarrow G):=minv∈ V(deg-(v)+deg+(v)) ≥ 3(3k-1)/2 has a \overrightarrow C3-factor, where \overrightarrow C3 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 \overrightarrow G on 3k vertices with minimum total degree δt(\overrightarrow G)≥ 4k-1 has a factor consisting of a copies of \overrightarrow T3 and b copies of \overrightarrow C3, where \overrightarrow T3 is the transitive tournament on three vertices. In particular, using b=0, there is a \overrightarrow T3-factor of \overrightarrow G , and using a=1, it is possible to obtain a \overrightarrow C3-factor of \overrightarrow G by reversing just one edge of \overrightarrow G. All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph \overrightarrow G on 3k vertices with minimum semidegree δ0(\overrightarrow G):=minv∈ Vmin(deg-(v),deg+(v)) ≥ 2k has a \overrightarrow C3-factor, and prove that this is asymptotically correct.