Kelmans–Seymour-sejtés
A matematika, azon belül a gráfelmélet területén a Kelmans–Seymour-sejtés kimondja, hogy bármely 5-szörösen összefüggő gráf, ami nem rajzolható síkba, tartalmazza homeomorf részgráfként a K5 5 csúcsú teljes gráfot. A sejtés nevét Paul Seymour és Alexander Kelmans matematikusokról kapta, akik egymástól függetlenül megfogalmazták – Seymour 1977-ben, Kelmans 1979-ben.[1]
A Kuratowski-tétel szerint egy síkba nem rajzolható gráf szükségképpen tartalmazza homeomorf részgráfként vagy a K5 teljes gráfot, vagy a K3,3 teljes páros gráfot. A Kelmans–Seymour-sejtés pontosítja ezt egy olyan feltétel megadásával, ami garantálja a két gráf közül az egyik létezését. Ebben az értelemben a Wagner-tétel topologikus minor-analógiája; a Wagner-tétel kimondja, hogy a 4-szeresen összefüggő síkba nem rajzolható gráfok tartalmazzák K5-t gráfminorként..
2016-ban a Georgia Tech matematikaprofesszora, Xingxing Yu és két PhD hallgatója, Dawei He és Yan Wang bejelentették a sejtés bizonyítását. Bizonyításuk online hozzáférhető.[2][3]
A tétel precíz megfogalmazása szerkesztés
Minden 5-szörösen összefüggő nem síkbarajzolható gráf tartalmazza homeomorf részgráfként a K5 teljes gráfot.
Kapcsolódó szócikkek szerkesztés
Jegyzetek szerkesztés
- ↑ Condie, Bill (May 30, 2016), "Maths mystery solved after 40 years", Cosmos, <https://cosmosmagazine.com/mathematics/maths-mystery-solved-after-40-years>.
- ↑ He, Dawei (2015. november 16.). „The Kelmans-Seymour conjecture I: special separations”. arXiv:1511.05020 [math].
- ↑ He, Dawei (2016. február 24.). „The Kelmans-Seymour conjecture II: 2-vertices in $K_4^-$”. arXiv:1602.07557 [math].