Seymour conjectured that a graph of order with minimum vertex degree contains the th graph power of a Hamiltonian cycle, generalizing Pósa's Conjecture. Komlós et al. (1998) proved the conjecture for sufficiently large using Szemerédi's regularity lemma and a technique called the blow-up lemma.
Seymour Conjecture
See also
Hajnal-Szemerédi Theorem, Hamiltonian Cycle, Pósa's Conjecture, Pósa's Theorem, Szemerédi's Regularity LemmaExplore with Wolfram|Alpha
References
Faudree, R. J.; Gould, R. J.; Jacobson, M. S.; and Schelp, R. H. "On a Problem of Paul Seymour." In Recent Advances in Graph Theory (Ed. V. R. Kulli). Vishwa International Publishers, pp. 197-215, 1991.Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "On the Square of a Hamiltonian Cycle in Dense Graphs." In Random Structures Algorithms 9, 193-211, 1996.Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "Proof of the Seymour Conjecture for Large Graphs." Ann. Comb. 2, 43-60, 1998.Seymour, P. Problem Section in Combinatorics: Proceedings of the British Combinatorial Conference, 1973 (Ed. T. P. McDonough and V. C. Mavron). Cambridge, England: Cambridge University Press, pp. 201-202, 1974.Referenced on Wolfram|Alpha
Seymour ConjectureCite this as:
Weisstein, Eric W. "Seymour Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SeymourConjecture.html