TOPICS
Search

Seymour Conjecture


Seymour conjectured that a graph G of order n with minimum vertex degree delta(G)>=kn/(k+1) contains the kth graph power of a Hamiltonian cycle, generalizing Pósa's Conjecture. Komlós et al. (1998) proved the conjecture for sufficiently large n using Szemerédi's regularity lemma and a technique called the blow-up lemma.


See also

Hajnal-Szemerédi Theorem, Hamiltonian Cycle, Pósa's Conjecture, Pósa's Theorem, Szemerédi's Regularity Lemma

Explore 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 Conjecture

Cite this as:

Weisstein, Eric W. "Seymour Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SeymourConjecture.html

Subject classifications