An extension of the Hajnal-Szemerédi theorem to directed graphs

DOI10.1017/S0963548314000716MaRDI QIDQ5364255zbMATH OpenOpenAlexFDO

Authors Louis DeBiasio, Theodore Molla, Andrzej Czygrinow, H. A. Kierstead

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/1307.4803

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35)

Abstract: Hajnal and Szemeredi proved that every graph G with |G|=ks and minimum degree at least k(s-1) contains k vertex disjoint s-cliques; moreover this degree bound is optimal. We extend their theorem to directed graphs by showing that every directed graph D with |D|=ks and minimum (total) degree at least 2k(s-1)-1 contains k vertex disjoint transitive tournaments on s vertices. Our result implies the Hajnal-Szemeredi Theorem, and the degree bound is optimal. We also make some conjectures regarding even more general results for multigraphs and partitioning into other tournaments. One of these conjectures is supported by an asymptotic result.

Recommendations

• On directed versions of the Hajnal-Szemerédi theorem
• Tiling directed graphs with tournaments
• A degree sequence Hajnal-Szemerédi theorem
• On directed versions of the Corrádi-Hajnal corollary
• Variants of the Hajnal-Szemer�di Theorem

Cites work

• A fast algorithm for equitable coloring
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A proof of Sumner's universal tournament conjecture for large tournaments
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• An Ore-type theorem on equitable coloring
• Extremal graph packing problems: Ore-type versus Dirac-type
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• scientific article; zbMATH DE number 4191728 (Why is no real title available?)
• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 3902685 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• scientific article; zbMATH DE number 3353327 (Why is no real title available?)
• Independent directed triangles in a directed graph
• Largest digraphs contained in all n-tournaments
• On directed versions of the Corrádi-Hajnal corollary
• On the existence of disjoint cycles in a graph
• On the maximal number of independent circuits in a graph
• On the square of a Hamiltonian cycle in dense graphs
• Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld's conjecture
• Some Theorems on Abstract Graphs
• Sufficient Conditions for Circuits in Graphs^†
• Triangle packings and 1-factors in oriented graphs

Cited in

(13)

• Duplication of directed graphs and exponential blow up of proofs
• Transitive triangle tilings in oriented graphs
• A degree sequence Hajnal-Szemerédi theorem
• Triangle factors of graphs without large independent sets and of weighted graphs
• Tiling directed graphs with tournaments
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• On directed versions of the Corrádi-Hajnal corollary
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• A discrepancy version of the Hajnal-Szemerédi theorem
• 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
• Rainbow spanning structures in graph and hypergraph systems

This page was built for publication: An extension of the Hajnal-Szemerédi theorem to directed graphs

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