Ramsey-Turán Type Problem for Perfect Transitive Triangle Tilings in Digraphs

Abstract

The classical Corrádi-Hajnal theorem states that for any multiple $n$ of $3$, if $G$ is a graph with $n$ vertices and $\hat{I}´(G)\ge 2n/3$, then $G$ can be partitioned into $n/3$ vertex-disjoint copies of the triangle [\emph{Acta Math. Acad. Sci. Hung.}, 14:423-439, 1964]. Balogh, Molla and Sharifzadeh obtained a smaller lower bound by adding the independence number condition [\emph{Random Struct. Algorithms}, 49:669-693, 2016]. In this paper, we study perfect tilings in digraphs subject to conditions on the independence number and the degree. The independence number, $\hat{I}\pm (D)$, of $D$ is the maximum integer $k$ such that $D$ has an independent set of cardinality $k$. We show that if $D$ is an $n$-vertex digraph with $\hat{I}\pm (D)\le o(1)n$ and $\hat{I}´(D)\ge (1+o(1))n$, then $D$ has a perfect $T_3$-tiling, where $T_3$ denotes a transitive triangle. This minimum degree condition is asymptotically best possible. Moreover, our result implies the theorem of Balogh, Molla, and Sharifzadeh concerning perfect triangle tilings.

19 pages, 3 figures