Transitive Triangle Tilings in Oriented Graphs

Abstract

In this paper, we prove an analogue of Corrádi and Hajnal's classical theorem. There exists $n_0$ such that for every $n\in 3\mathbb{Z}$ when $n\ge n_0$ the following holds. If $G$ is an oriented graph on $n$ vertices and every vertex has both indegree and outdegree at least $7n/18$, then $G$ contains a perfect transitive triangle tiling, which is a collection of vertex-disjoint transitive triangles covering every vertex of $G$. This result is best possible, as, for every $n\in 3\mathbb{Z}$, there exists an oriented graph $G$ on $n$ vertices without a perfect transitive triangle tiling in which every vertex has both indegree and outdegree at least $\lceil 7n/18\rceil -1.$

To appear in Journal of Combinatorial Theory, Series B (JCTB)

References in corpus (1)

• An extension of the Hajnal-Szemeredi theorem to directed graphs

Cited by in corpus (1)

• A degree sequence Hajnal--Szemerédi theorem