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

• 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?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• A fast algorithm for equitable coloring
• A proof of Sumner's universal tournament conjecture for large tournaments
• An Ore-type theorem on equitable coloring
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Extremal graph packing problems: Ore-type versus Dirac-type
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• 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)

• Transitive tournament tilings in oriented graphs with large minimum total degree
• Triangle factors of graphs without large independent sets and of weighted graphs
• Rainbow spanning structures in graph and hypergraph systems
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• A discrepancy version of the Hajnal-Szemerédi theorem
• A degree sequence Hajnal-Szemerédi theorem
• On directed versions of the Corrádi-Hajnal corollary
• Duplication of directed graphs and exponential blow up of proofs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Tiling directed graphs with tournaments
• On directed versions of the Hajnal-Szemerédi theorem
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Transitive triangle tilings in oriented graphs

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)