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 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..
A Kuratowski-tétel szerint egy síkba nem rajzolható gráf szükségképpen tartalmazza homeomorf részgráfként vagy a teljes gráfot, vagy a 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 -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ő.
A tétel precíz megfogalmazása Minden 5-szörösen összefüggő nem síkbarajzolható gráf tartalmazza homeomorf részgráfként a teljes gráfot.
Kapcsolódó szócikkek Négyszíntétel Kuratowski-tétel Hajós-sejtés
Jegyzetek
Kategória:Síkgráfok Kategória:Gráfelméleti tételek