Hadwiger gissning (grafteori)

Hadwiger-förmodan (grafteorin) är en av grafteorins olösta hypoteser . Den är formulerad enligt följande: varje kromatisk graf är sammandragbar till en komplett graf på hörn. $k$ $k$

Annan formulering

Hadwigers gissning kan formuleras annorlunda: i varje kromatisk graf finns det nödvändigtvis icke-korsande sammankopplade subgrafer så att det finns en kant mellan två av dem. $k$ $k$

Om vi för grafen introducerar Hadwiger-talet — det maximala så att vi drar ihop oss till hela grafen vid hörnen, då formuleras hypotesen som olikheten , där är grafens kromatiska tal . $h(G)$ $k$ $G$ $k$ $\chi(G) \leqslant h(G)$ $\chi (G)$

Specialfall

Fallen och är uppenbara: i det första fallet innehåller grafen minst en kant, vilket är hela grafen , i det andra fallet är grafen inte tvådelad och innehåller en cykel som är sammandragbar till . $k=2$ $k = 3$ $K_{2}$ $K_{3}$

Beviset i fallet publicerades av Hadwiger själv i samma tidning som gissningen ställdes i. $k = 4$

Från Hadwiger-förmodan i fallet följer giltigheten av problemet med fyra färger (nu bevisat): sammandragningsoperationen bevarar planariteten , och om det fanns en plan 5-kromatisk graf skulle det finnas en inbäddning av grafen i planet , vars obefintlighet följer av Eulers formel . 1937 bevisade Klaus Wagner likvärdigheten mellan fyrafärgsproblemet och Hadwiger-förmodan för , så detta fall är också bevisat. $k = 5$ $K_{5}$ $k = 5$

1993 bevisade N. Robertson, P. Seymour och Robin Thomas gissningen för att använda fyrfärgsproblemet. [1] Detta bevis vann 1994 års Fulkerson-pris . $k = 6$

För det är känt att om grafen inte uppfyller hypotesen, så är den sammandragbar både till och för att komplettera tvådelade grafer med delar av kardinalitet 4 respektive 4 och kardinalitet 3 respektive 5. $k = 7$ $K_{4,4}$ $K_{3,5}$

Hadwiger nummer

Det är möjligt att definiera en mappning som tilldelar en maximal graf så att vi drar ihop oss till hela grafen vid hörnen. Att hitta Hadwiger-talet för en given graf är ett NP-svårt problem . I vilken graf som helst för vilken det finns en gradpunkt . [2] Genom att tillämpa en girig graffärgningsalgoritm kan man dra slutsatsen från detta påstående att . $h(G)$ $G$ $k$ $G$ $k$ $G$ $h(G) = k$ $O(k \sqrt{\log k})$ $\chi (G) = O(h(G) \sqrt {\log h(G)})$

Se även

Hadwigers gissning (kombinatorisk geometri)

Anteckningar

↑ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "Hadwigers gissning för K6-fria grafer" Arkiverad 10 april 2009 på Wayback Machine
↑ Kostochka, AV (1984), "Nedre gränsen för Hadwiger-antalet grafer efter deras genomsnittliga grad"