On the Turánability and tileability of oriented graphs

2025/07/17 by Igor Araújo, Araujo, Igor, Zimu Xiang +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2507.13267

Abstract

An oriented graph H is Turánable (resp. tileable) if there exist n₀ ∈ ℕ such that every semi-regular near-tournament on n ≥ n₀ vertices contains a copy of H (resp. a perfect H-tiling). We disprove a conjectured characterization of Turánable oriented graphs by DeBiasio, Han, Lo, Molla, Piga, and Treglown, show that there are Turánable oriented graphs which are not tileable, and provide a new example of tileable oriented graph.

Citations

• Powers of Hamilton cycles in oriented and directed graphs
• Cycle-factors in oriented graphs
• Tiling edge-ordered graphs with monotone paths and other structures
• Turán problems for Edge-ordered graphs
• Cyclic triangle factors in regular tournaments
• Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs
• F-factors in hypergraphs via absorption
• Triangle packings and 1-factors in oriented graphs
• A Dirac type result on Hamilton cycles in oriented graphs
• The minimum degree threshold for perfect graph packings

Related

• A note on some embedding problems for oriented graphs
• Turán problems for oriented graphs
• Transitive tournament tilings in oriented graphs with large minimum total degree
• Unavoidable trees in tournaments
• Transitive Triangle Tilings in Oriented Graphs