Tiling directed graphs with tournaments

DOI10.1017/FMS.2018.2MaRDI QIDQ3119461zbMATH OpenOpenAlexFDO

Authors Louis DeBiasio, Theodore Molla, Andrew Treglown, Andrzej Czygrinow

Publication date 12 March 2019

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1603.08198

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The Hajnal--Szemer'edi theorem states that for any integer $rge1$ and any multiple $n$ of $r$, if $G$ is a graph on $n$ vertices and $delta(G)ge(1-1/r)n$, then $G$ can be partitioned into $n/r$ vertex-disjoint copies of the complete graph on $r$ vertices. We prove a very general analogue of this result for directed graphs: for any integer $rge4$ and any sufficiently large multiple $n$ of $r$, if $G$ is a directed graph on $n$ vertices and every vertex is incident to at least $2(1-1/r)n-1$ directed edges, then $G$ can be partitioned into $n/r$ vertex-disjoint subgraphs of size $r$ each of which contain every tournament on $r$ vertices. A related Tur'an-type result is also proven.

Recommendations

• On directed versions of the Hajnal-Szemerédi theorem
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• Tiling transitive tournaments and their blow-ups
• Transitive triangle tilings in oriented graphs
• Transitive tournament tilings in oriented graphs with large minimum total degree

Cites work

• \(F\)-factors in hypergraphs via absorption
• A degree sequence Hajnal-Szemerédi theorem
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A multipartite Hajnal-Szemerédi theorem
• A note on some embedding problems for oriented graphs
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Almost \(H\)-factors in dense graphs
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• An Ore-type theorem on equitable coloring
• Critical chromatic number and the complexity of perfect packings in graphs
• Embedding large subgraphs into dense graphs
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3333210 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Large vertex-disjoint cycles in a bipartite graph
• Monochromatic cycles in 2-coloured graphs
• On directed versions of the Corrádi-Hajnal corollary
• On directed versions of the Hajnal-Szemerédi theorem
• On the Complexity of General Graph Factor Problems
• On the maximal number of independent circuits in a graph
• Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld's conjecture
• Proof of the Alon-Yuster conjecture
• The extremal function for partial bipartite tilings
• The minimum degree threshold for perfect graph packings
• Tiling transitive tournaments and their blow-ups
• Tiling Turán theorems
• Transitive triangle tilings in oriented graphs
• Triangle packings and 1-factors in oriented graphs

Cited in

(12)

• Tiling transitive tournaments and their blow-ups
• Transitive triangle tilings in oriented graphs
• Cyclic triangle factors in regular tournaments
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• A discrepancy version of the Hajnal-Szemerédi theorem
• Dirac-type results for tilings and coverings in ordered graphs
• A degree sequence Komlós theorem
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• On directed versions of the Hajnal-Szemerédi theorem
• Transitive tournament tilings in oriented graphs with large minimum total degree
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Sufficient conditions for perfect mixed tilings

This page was built for publication: Tiling directed graphs with tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3119461)