Abstract
Paul Seymour conjectured that any graphG of ordern and minimum degree of at leastk/k+1n contains thekth power of a Hamiltonian cycle. Here, we prove this conjecture for sufficiently largen.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978.
G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc.2 (1952) 68–81.
G. Fan and R. Häggkvist, The square of a hamiltonian cycle, SIAM J. Discrete Math., to appear.
G. Fan and H.A. Kierstead, The square of paths and cycles, manuscript.
G. Fan and H.A. Kierstead, The square of paths and cycles, J. Combin. Theory Ser. B63 (1995) 55–64.
G. Fan and H.A. Kierstead, Hamiltonian square-paths, J. Combin. Theory Ser. B67 (1996) 167–182.
R.J. Faudree, R.J. Gould, and M. Jacobson, On a problem of Pósa and Seymour, private communication, 1992.
R.J. Faudree, R.J. Gould, M.S. Jacobson, and R.H. Schelp, On a problem of Paul Seymour, In: Recent Advances in Graph Theory, V.R. Kulli, Ed., Vishwa International Publication, 1991, pp. 197–215.
R. Häggkvist, OnF-hamiltonian graphs, In: Graph Theory and Related Topics, J.A. Bondy and U.S.R. Murty, Eds., Academic Press, New York, 1979, pp. 219–231.
A. Hajnal and E. Szemerédi, Proof of a conjecture of Erdős, In: Combinatorial Theory and Its Applications, Vol. II, P. Erdős, A. Rényi, and V.T. Sós, Eds., Colloq. Math. Soc. J. Bolyai4, North-Holland, Amsterdam, 1970, pp. 601–623.
J. Komlós, G.N. Sárközy, and E. Szemerédi, Proof of a packing conjecture of Bollobás, Combin. Probab. Comput.4 (1995) 241–255.
J. Komlós, G.N. Sárközy, and E. Szemerédi, Blow-up Lemma, Combinatorica17 (1997) 109–123.
J. Komlós, G.N. Sárközy, and E. Szemerédi, On the square of a Hamiltonian cycle in dense graphs, Random Structures and Algorithms9 (1996) 193–211.
J. Komlós, G.N. Sárközy, and E. Szemerédi, On the Pósa-Seymour conjecture, J. Graph Theory, to appear.
J. Komlós, G.N. Sárközy, and E. Szemerédi, An algorithmic version of the Blow-up Lemma, Random Structures and Algorithms, to appear.
P. Seymour, Problem section, In: Combinatorics: Proceedings of the British Combinatorial Conference 1973, T.P. McDonough and V.C. Mavron, Eds., Cambridge University Press, 1974, pp. 201–202.
E. Szemerédi, Regular partitions of graphs, In: Colloques Internationaux C.N.R.S. N° 260 — Problèmes Combinatoires et Théorie des Graphes, Orsay, 1976, pp. 399–401.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Komlós, J., Sárközy, G.N. & Szemerédi, E. Proof of the Seymour conjecture for large graphs. Annals of Combinatorics 2, 43–60 (1998). https://doi.org/10.1007/BF01626028
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01626028