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  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. Ebban 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

Síkgráfok
Gráfelméleti tételek
A matematika , azon belül a gráfelmélet területén a Kelmans–Seymour-sejtés kimondja , hogy bármelyszörösen összefüggő gráf , ami nem rajzolható síkba , tartalmazza homeomorf részgráfként a 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 – Seymourben , Kelmansben . 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 . Ebban az értelemben a Wagner-tétel topologikus minor-analógiája ; a Wagner-tétel kimondja , hogy aszeresen ö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 Mindenszö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 Síkgráfok Gráfelméleti tételek