Annals of Combinatorics 2 (1998) 43-60


Proof of the Seymour Conjecture for Large Graphs

János Komlós, Gábor N. Sárközy, and Endre Szemerédi

Department of Mathematics, Rutgers University, New Brunswick, NJ 08930, USA
komlos@math.rutgers.edu

Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA
gsarkozy@cs.wpi.edu

Computer Science Department, Rutgers University, New Brunswick, NJ 08930, USA
szemered@cs.rutgers.edu

Received December 5, 1997

AMS Subject Classification: 05C45

Abstract. Paul Seymour conjectured that any graph G of order n and minimum degree of at least k/(k+1) n contains the kth power of a Hamiltonian cycle. Here, we prove this conjecture for sufficiently large n.

Keywords: dense graphs, powers of Hamiltonian cycles


References

1.  B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978.

2.  G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 68–81.

3.  G. Fan and R. Häggkvist, The square of a hamiltonian cycle, SIAM J. Discrete Math., to appear.

4.  G. Fan and H.A. Kierstead, The square of paths and cycles, manuscript.

5.  G. Fan and H.A. Kierstead, The square of paths and cycles, J. Combin. Theory Ser. B 63 (1995) 55–64.

6.  G. Fan and H.A. Kierstead, Hamiltonian square-paths, J. Combin. Theory Ser. B 67 (1996) 167–182.

7.  R.J. Faudree, R.J. Gould, and M. Jacobson, On a problem of Pósa and Seymour, private communication, 1992.

8.  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.

9.  R. Häggkvist, On F-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.

10.  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. Bolyai 4, North-Holland, Amsterdam, 1970, pp. 601–623.

11.  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.

12.  J. Komlós, G.N. Sárközy, and E. Szemerédi, Blow-up Lemma, Combinatorica 17 (1997) 109–123.

13.  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 Algorithms 9 (1996) 193–211.

14.  J. Komlós, G.N. Sárközy, and E. Szemerédi, On the Pósa-Seymour conjecture, J. Graph Theory, to appear.

15.  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.

16.  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.

17.  E. Szemerédi, Regular partitions of graphs, In: Colloques Internationaux C.N.R.S. No 260 - Problèmes Combinatoires et Théorie des Graphes, Orsay, 1976, pp. 399–401.


Get the LaTex | DVI | PS file of this abstract.

back