pith. sign in

arxiv: 1401.0460 · v2 · pith:W3ZOQOOHnew · submitted 2014-01-02 · 🧮 math.CO

Transitive Triangle Tilings in Oriented Graphs

classification 🧮 math.CO
keywords everytransitiveorientedtrianglevertexexistsgraphindegree
0
0 comments X
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.