An extension of the Hajnal-Szemerédi theorem to directed graphs
From MaRDI portal
Publication:5364255
DOI10.1017/S0963548314000716zbMATH Open1371.05101arXiv1307.4803OpenAlexW2162255574MaRDI QIDQ5364255FDOQ5364255
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)
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.
Full work available at URL: https://arxiv.org/abs/1307.4803
Recommendations
Cites Work
- An Ore-type theorem on equitable coloring
- A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
- On directed versions of the Corrádi-Hajnal corollary
- Title not available (Why is that?)
- On the maximal number of independent circuits in a graph
- How to avoid using the regularity Lemma: Pósa's conjecture revisited
- Some Theorems on Abstract Graphs
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the square of a Hamiltonian cycle in dense graphs
- A proof of Sumner's universal tournament conjecture for large tournaments
- Title not available (Why is that?)
- On the existence of disjoint cycles in a graph
- An exact minimum degree condition for Hamilton cycles in oriented graphs
- Extremal graph packing problems: Ore-type versus Dirac-type
- A fast algorithm for equitable coloring
- Sufficient Conditions for Circuits in Graphs†
- Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld's conjecture
- Triangle packings and 1-factors in oriented graphs
- Independent directed triangles in a directed graph
- Title not available (Why is that?)
- Largest digraphs contained in all n-tournaments
Cited In (12)
- On Directed Versions of the Hajnal–Szemerédi Theorem
- A discrepancy version of the Hajnal–Szemerédi theorem
- Duplication of directed graphs and exponential blow up of proofs
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- A degree sequence 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
- Rainbow spanning structures in graph and hypergraph systems
- Transitive triangle tilings in oriented graphs
- Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
- Transitive Tournament Tilings in Oriented Graphs with Large Minimum Total Degree
- TILING DIRECTED GRAPHS WITH TOURNAMENTS
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)
