Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T11:47:41.067Z Has data issue: false hasContentIssue false
  • English
  • Français

An Extension of the Hajnal–Szemerédi Theorem to Directed Graphs

Published online by Cambridge University Press:  28 October 2014

ANDRZEJ CZYGRINOW,
LOUIS DeBIASIO,
H. A. KIERSTEAD and
THEODORE MOLLA
ANDRZEJ CZYGRINOW
Affiliation:
School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ 85287, USA (e-mail: aczygri@asu.edu, kierstead@asu.edu)
LOUIS DeBIASIO
Affiliation:
Miami University, Oxford, OH 45056, USA (e-mail: debiasld@miamioh.edu)
H. A. KIERSTEAD
Affiliation:
School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ 85287, USA (e-mail: aczygri@asu.edu, kierstead@asu.edu)
THEODORE MOLLA
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: molla@illinois.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Hajnal and Szemerédi proved that every graph G with |G| = ks and δ(G)⩾ k(s − 1) contains k disjoint s-cliques; moreover this degree bound is optimal. We extend their theorem to directed graphs by showing that every directed graph $\vv G$ with | $\vv G$ | = ks and δ( $\vv G$ ) ⩾ 2k(s − 1) − 1 contains k disjoint transitive tournaments on s vertices, where δ( $\vv G$ )= minv∈V ( $\vv G$ )d −(v)+d +(v). Our result implies the Hajnal–Szemerédi theorem, and its 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.

Keywords

Primary 05C20Secondary 05C35

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 5 , September 2015, pp. 754 - 773
Copyright
Copyright © Cambridge University Press 2014 

References

[1] Chernoff, H. (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23 493–507.CrossRefGoogle Scholar
[2] Corrádi, K. and Hajnal, A. (1963) On the maximal number of independent circuits in a graph. Acta Math. Hungar. 14 423–439.CrossRefGoogle Scholar
[3] Czygrinow, A., Kierstead, H. A. and Molla, T. (2014) On directed versions of the Corrádi–Hajnal corollary. European J. Combin. 42 1–14.CrossRefGoogle Scholar
[4] Dirac, G. A. (1952) Some theorems on abstract graphs. Proc. London Math. Soc. 3 69–81.CrossRefGoogle Scholar
[5] Enomoto, H. (1998) On the existence of disjoint cycles in a graph. Combinatorica 18 487–492.CrossRefGoogle Scholar
[6] Enomoto, H., Kaneko, A. and Tuza, Z. (1987) P 3-factors and covering cycles in graphs of minimum degree n/3. Combinatorics 52 213–220.Google Scholar
[7] Erdős, P. (1963) Problem 9. In Theory of Graphs and its Applications, Czechoslovak Academy of Sciences, Prague.Google Scholar
[8] Ghouila-Houri, A. (1960) Une condition suffisante d'existence d'un circuit hamiltonien. CR Math. Acad. Sci. Paris 25 495–497.Google Scholar
[9] Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of P. Erdős. In Combinatorial Theory and its Applications, Vol. 2, North-Holland, pp. 601–623.Google Scholar
[10] Havet, F. and Thomassé, S. (2000) Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld's conjecture. J. Combin. Theory Ser. B 78 243–273.CrossRefGoogle Scholar
[11] Keevash, P., Kuhn, D. and Osthus, D. (2009) An exact minimum degree condition for Hamilton cycles in oriented graphs. J. London Math. Soc. 79 144–166.CrossRefGoogle Scholar
[12] Keevash, P. and Sudakov, B. (2009) Triangle packings and 1-factors in oriented graphs. J. Combin. Theory Ser. B 99 709–727.CrossRefGoogle Scholar
[13] Kierstead, H. A. and Kostochka, A. V. (2008) A short proof of the Hajnal–Szemerédi theorem on equitable colouring. Combin. Probab. Comput. 17 265–270.CrossRefGoogle Scholar
[14] Kierstead, H. A. and Kostochka, A. V. (2008) An Ore-type theorem on equitable coloring. J. Combin. Theory Ser. B 98 226–234.CrossRefGoogle Scholar
[15] Kierstead, H. A., Kostochka, A. V., Mydlarz, M. and Szemerédi, E. (2010) A fast algorithm for equitable coloring. Combinatorica 30 217–224.CrossRefGoogle Scholar
[16] Kierstead, H. A., Kostochka, A. V. and Yu, G. (2009) Extremal graph packing problems: Ore-type versus Dirac-type. In Surveys in Combinatorics 2009 (Huczynska, S., Mitchell, J. and Roney-Dougal, C., eds), Vol. 365 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 113–136.Google Scholar
[17] Komlós, J. and Sárközy, G. N. and Szemerédi, E. (1996) On the square of a Hamiltonian cycle in dense graphs. Random Struct. Alg. 9 193–211.3.0.CO;2-P>CrossRefGoogle Scholar
[18] Kühn, D., Mycroft, R. and Osthus, D. (2011) A proof of Sumner's universal tournament conjecture for large tournaments. Proc. London Math. Soc. 4 731–766.CrossRefGoogle Scholar
[19] Levitt, I., Sárközy, G. N. and Szemerédi, E. (2010) How to avoid using the regularity lemma: Pósa's conjecture revisited. Discrete Math. 310 630–641.CrossRefGoogle Scholar
[20] Linial, N., Saks, M. and Sós, V. T. (1983) Largest digraphs contained in all n-tournaments. Combinatorica 3 101–104.CrossRefGoogle Scholar
[21] Nash-Williams, C. St J. A. (1971) Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency. In Studies in Pure Mathematics (presented to Richard Rado), Academic Press, pp. 157–183.Google Scholar
[22] Saks, M. and Sós, V. T. (1981) On unavoidable subgraphs of tournaments. Finite and Infinite Sets, Vol. 37 of Colloquia Mathematica Societatis János Bolyai, North-Holland, pp. 663–674.Google Scholar
[23] Wang, H. (2000) Independent directed triangles in directed graphs. Graphs Combin. 16 453–462.Google Scholar
[24] Woodall, D. (1972) Sufficient conditions for cycles in digraphs. Proc. London Math. Soc. 24 739–755.CrossRefGoogle Scholar