Transitive Triangle Tilings in Oriented Graphs
| Autor: | Balogh, József, Lo, Allan, Molla, Theodore |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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.$ Comment: To appear in Journal of Combinatorial Theory, Series B (JCTB) |
| Databáze: | arXiv |
| Externí odkaz: |
|