Hadwiger formodning (grafteori)

Hadwiger-formodningen (grafteori) er en af grafteoriens uafklarede hypoteser . Den er formuleret som følger: hver -kromatisk graf kan trækkes sammen til en komplet graf på hjørner. $k$ $k$

Anden formulering

Hadwigers formodning kan formuleres forskelligt: I hver kromatisk graf eksisterer der nødvendigvis ikke-skærende forbundne subgrafer , således at der er en kant mellem to af dem. $k$ $k$

Hvis vi indfører for grafen Hadwiger-tallet - det maksimale , således at vi trækker os sammen til den komplette graf ved hjørnerne, så formuleres hypotesen som uligheden , hvor er grafens kromatiske tal . $h(G)$ $k$ $G$ $k$ $\chi(G) \leqslant h(G)$ $\chi (G)$

Særlige tilfælde

Tilfældene og er indlysende: i det første tilfælde indeholder grafen mindst én kant, som er den komplette graf , i det andet tilfælde er grafen ikke todelt og indeholder en cyklus, der kan trækkes sammen til . $k=2$ $k = 3$ $K_{2}$ $K_{3}$

Beviset i sagen blev offentliggjort af Hadwiger selv i det samme blad, hvori formodningen blev stillet. $k = 4$

Fra Hadwiger-formodningen i sagen følger gyldigheden af problemet med fire farver (nu bevist): sammentrækningsoperationen bevarer planariteten , og hvis der var en plan 5-kromatisk graf, ville der være en indlejring af grafen i planet , hvis ikke-eksistens følger af Euler-formlen . I 1937 beviste Klaus Wagner ækvivalensen af firefarveproblemet og Hadwiger-formodningen for , så denne sag er også bevist. $k = 5$ $K_{5}$ $k = 5$

I 1993 beviste N. Robertson, P. Seymour og Robin Thomas formodningen om at bruge firefarveproblemet. [1] Dette bevis vandt 1994 Fulkerson Prize . $k = 6$

For det er kendt, at hvis grafen ikke opfylder hypotesen, så er den kontraherbar både til og til - at færdiggøre todelte grafer med dele af henholdsvis kardinalitet 4 og 4 og kardinalitet 3 og 5. $k = 7$ $K_{4,4}$ $K_{3,5}$

Hadwiger nummer

Det er muligt at definere en mapping , der tildeler en maksimal graf, således at vi trækker sig sammen til den komplette graf ved hjørnerne. At finde Hadwiger-tallet for en given graf er et NP-svært problem . I enhver graf , hvor der findes et toppunkt af grad . [2] Ved at anvende en grådig graffarvealgoritme kan det udledes af denne erklæring, at . $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 også

Hadwigers formodning (kombinatorisk geometri)

Noter

↑ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "Hadwigers formodning om K6-fri grafer" Arkiveret 10. april 2009 på Wayback Machine
↑ Kostochka, AV (1984), "Nedre grænse for Hadwiger-antallet af grafer efter deres gennemsnitlige grad"