On directed versions of the Hajnal-Szemerédi theorem

DOI10.1017/S0963548315000036MaRDI QIDQ5364261zbMATH OpenOpenAlexFDO

Authors Andrew Treglown

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We say that a (di)graph $G$ has a perfect $H$-packing if there exists a set of vertex-disjoint copies of $H$ which cover all the vertices in $G$. The seminal Hajnal--Szemer'edi theorem characterises the minimum degree that ensures a graph $G$ contains a perfect $K_r$-packing. In this paper we prove the following analogue for directed graphs: Suppose that $T$ is a tournament on $r$ vertices and $G$ is a digraph of sufficiently large order $n$ where $r$ divides $n$. If $G$ has minimum in- and outdegree at least $(1-1/r)n$ then $G$ contains a perfect $T$-packing. In the case when $T$ is a cyclic triangle, this result verifies a recent conjecture of Czygrinow, Kierstead and Molla (for large digraphs). Furthermore, in the case when $T$ is transitive we conjecture that it suffices for every vertex in $G$ to have sufficiently large indegree or outdegree. We prove this conjecture for transitive triangles and asymptotically for all $rgeq3$. Our approach makes use of a result of Keevash and Mycroft concerning almost perfect matchings in hypergraphs as well as the Directed Graph Removal lemma.

Recommendations

• A degree sequence Hajnal-Szemerédi theorem
• Tiling directed graphs with tournaments
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• On perfect packings in dense graphs
• A multipartite Hajnal-Szemerédi theorem

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A geometric theory for hypergraph matching
• A new proof of the graph removal lemma
• A note on some embedding problems for oriented graphs
• An Ore-type theorem for perfect packings in graphs
• An Ore-type theorem on equitable coloring
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• Disjoint directed quadrilaterals in a directed graph
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Independent directed triangles in a directed graph
• Minimum codegree threshold for (K^3_4-e)-factors
• On directed versions of the Corrádi-Hajnal corollary
• On the Complexity of General Graph Factor Problems
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Proof of the Seymour conjecture for large graphs
• Testing subgraphs in directed graphs
• The minimum degree threshold for perfect graph packings
• Triangle packings and 1-factors in oriented graphs
• Variants of the Hajnal-Szemer�di Theorem

Cited in

(16)

• Clique-factors in graphs with sublinear -independence number
• A degree sequence Hajnal-Szemerédi theorem
• On directed versions of the Corrádi-Hajnal corollary
• A multipartite Hajnal-Szemerédi theorem
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• Triangle factors of graphs without large independent sets and of weighted graphs
• Tiling directed graphs with tournaments
• Minimum number of edges guaranteeing the existence of a \(K_{1, t}\)-factor in a graph
• Rainbow spanning structures in graph and hypergraph systems
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• Embedding clique-factors in graphs with low \(\ell\)-independence number
• Transitive triangle tilings in oriented graphs
• \(H\)-factors in graphs with small independence number
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• A note on some embedding problems for oriented graphs
• Transitive tournament tilings in oriented graphs with large minimum total degree

This page was built for publication: On directed versions of the Hajnal-Szemerédi theorem

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