Hadwiger-sejtés (gráfelmélet)

Ez a szócikk Hadwiger gráfelméleti sejtéséről szól. Lásd még: Hadwiger-sejtés (kombinatorikus geometria)
Az ábrán látható gráf színezéséhez négy színre van szükség; látható továbbá négy összefüggő részgráfja, melyek minorként összehúzva teljes gráfot adnak, illusztrálva ezzel a Hadwiger-sejtés k = 4 esetét.

A matematika, azon belül a gráfelmélet területén a Hadwiger-sejtés szerint ha egy G irányítatlan gráf minden (jó) színezéséhez k vagy több színre van szükség (azaz kromatikus száma legalább k), akkor található G-ben k olyan összefüggő, diszjunkt részgráf, melyek páronként mind éllel vannak összekötve. Ha minden ilyen részgráfon belül élösszehúzást végzünk, akkor a részgráfok egy-egy csúccsá omlanak össze, ami azt jelenti, hogy a G gráf minorja a k csúcsú teljes gráf, Kk.

Ez a Hugo Hadwiger által 1943-ban kimondott sejtés a négyszíntétel messzemenő általánosítása, ami jelenleg is messze áll a megoldástól. (Bollobás, Catlin & Erdős 1980) „a gráfelmélet egyik legmélyebb megoldatlan problémájának” nevezi.[1]