Hadwigerův dohad (teorie grafů)

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. $k$ $k$

Jiné znění

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. $k$ $k$

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. $h(G)$ $k$ $G$ $k$ $\chi(G) \leqslant h(G)$ $\chi (G)$

Speciální případy

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 . $k=2$ $k = 3$ $K_{2}$ $K_{3}$

Důkaz v případu zveřejnil sám Hadwiger ve stejném dokumentu, ve kterém byla domněnka předložena. $k = 4$

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. $k = 5$ $K_{5}$ $k = 5$

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 . $k = 6$

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í. $k = 7$ $K_{4,4}$ $K_{3,5}$

Hadwigerovo číslo

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 . $h(G)$ $G$ $k$ $G$ $k$ $G$ $h(G) = k$ $O(k \sqrt{\log k})$ $\chi (G) = O(h(G) \sqrt {\log h(G)})$

Viz také

Hadwigerova domněnka (kombinatorická geometrie)

Poznámky

↑ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), „Hadwigerova domněnka pro grafy bez K6“ Archivováno 10. dubna 2009 na Wayback Machine
↑ Kostochka, AV (1984), "Dolní mez Hadwigerova počtu grafů podle jejich průměrného stupně"