Kelmans–Seymour conjecture

In graph theory, the Kelmans–Seymour conjecture states that every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex complete graph K5. It is named for Paul Seymour and Alexander Kelmans, who independently described the conjecture; Seymour in 1977 and Kelmans in 1979.[1]

By Kuratowski's theorem, a nonplanar graph necessarily contains a subdivision of either K5 or the complete bipartite graph K3,3. The conjecture refines this by providing a condition under which one of these two graphs can be guaranteed to exist. In this sense, it is the analogue for topological minors of Wagner's theorem that 4-connected nonplanar graphs contain K5 as a graph minor.

In 2016, a proof was claimed by Xingxing Yu, Georgia Tech mathematics professor and his Ph.D. students Dawei He and Yan Wang.[2][3]

Precise formulation of the theorem

Every 5-connected nonplanar graph contains a subdivision of K5.

See also

References

  1. ↑ Condie, Bill (May 30, 2016), "Maths mystery solved after 40 years", Cosmos.
  2. ↑ He, Dawei; Wang, Yan; Yu, Xingxing (2015-11-16). "The Kelmans-Seymour conjecture I: special separations". arXiv:1511.05020Freely accessible [math.CO].
  3. ↑ He, Dawei; Wang, Yan; Yu, Xingxing (2016-02-24). "The Kelmans-Seymour conjecture II: 2-vertices in $K_4^-$". arXiv:1602.07557Freely accessible [math.CO].
This article is issued from Wikipedia - version of the 7/12/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.