Hadwigerova domněnka (teorie grafů) je jednou z nevyřešených hypotéz teorie grafů . Je formulován následovně: každý -chromatický graf je kontrahovatelný na úplný graf na vrcholech.
Hadwigerovu domněnku lze formulovat různě: v každém -chromatickém grafu nutně existují neprotínající se spojené podgrafy tak, že mezi libovolnými dvěma z nich je hrana.
Zavedeme-li do grafu Hadwigerovo číslo — maximum takové, že se zkrátíme na celý graf ve vrcholech, pak je hypotéza formulována jako nerovnost , kde je chromatické číslo grafu.
Případy a jsou zřejmé: v prvním případě graf obsahuje alespoň jednu hranu, která je úplným grafem , ve druhém případě graf není bipartitní a obsahuje cyklus smrštitelný na .
Důkaz v případu zveřejnil sám Hadwiger ve stejném dokumentu, ve kterém byla domněnka předložena.
Z Hadwigerovy domněnky v případě vyplývá platnost problému čtyř barev (nyní prokázáno): operace kontrakce zachovává rovinnost a pokud by existoval rovinný 5-chromatický graf, došlo by k vnoření grafu do roviny , jehož neexistence vyplývá z Eulerovy formule . V roce 1937 Klaus Wagner prokázal ekvivalenci problému čtyř barev a Hadwigerovy domněnky pro , takže tento případ je také prokázán.
V roce 1993 N. Robertson, P. Seymour a Robin Thomas dokázali domněnku pro použití problému čtyř barev. [1] Tento důkaz vyhrál v roce 1994 Fulkersonovu cenu .
Je totiž známo, že pokud graf nesplňuje hypotézu, pak je kontrahovatelný jak na, tak na - dokončit bipartitní grafy s částmi mohutnosti 4 a 4 a mohutnosti 3 a 5, v tomto pořadí.
Je možné definovat mapování , které přiřadí maximální graf tak, že se smrštíme na celý graf ve vrcholech. Najít Hadwigerovo číslo daného grafu je NP-těžký problém . V každém grafu , pro který existuje vrchol stupně . [2] Aplikujeme - li algoritmus barvícího grafu , lze z tohoto tvrzení odvodit, že .