Transitive Triangle Tilings in Oriented Graphs
classification
🧮 math.CO
keywords
everytransitiveorientedtrianglevertexexistsgraphindegree
read the original abstract
In this paper, we prove an analogue of Corr\'adi 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.$
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.