Heawood gissningar
Inom grafteori ger Heawoods gissning eller Ringel-Youngs teorem en nedre gräns för antalet färger som är nödvändiga för graffärgning på en yta av ett givet släkte . För ytor av släktet 0, 1, 2, 3, 4, 5, 6, 7, ... är det nödvändiga antalet färger 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS : A000934 , det kromatiska numret eller Heawood-numret.
Gissningen formulerades 1890 av Percy John Heawood och bevisades 1968 av Gerhard Ringel och Ted Youngs . Ett fall, den icke-orienterbara Klein-flaskan , visade sig vara ett undantag från den allmänna formeln. Ett helt annat tillvägagångssätt behövdes för det mycket äldre problemet att hitta antalet färger som behövs för planet eller sfären , löst 1976 som fyrafärgssatsen av Haken och Appel . På sfären är den nedre gränsen lätt, medan den övre gränsen för högre släkten är enkel och bevisades i Heawoods ursprungliga korta papper som innehöll gissningen. Med andra ord, Ringel, Youngs och andra var tvungna att konstruera extrema exempel för varje släkte g = 1,2,3,.... Om g = 12s + k, faller släktena in i 12 fall enligt k = 0,1, 2,3,4,5,6,7,8,9,10,11. För att förenkla, anta att fallet k har fastställts om bara ett ändligt antal g av formen 12s + k är osäker. Sedan åren då de tolv målen avgjordes och av vem är följande:
- 1954, Ringel: fall 5
- 1961, Ringel: fall 3,7,10
- 1963, Terry, Welch, Youngs: fall 0,4
- 1964, Gustin, Youngs: fall 1
- 1965, Gustin: fall 9
- 1966, Youngs: fall 6
- 1967, Ringel, Youngs: fall 2,8,11
De senaste sju sporadiska undantagen avgjordes enligt följande:
- 1967, Mayer: fall 18, 20, 23
- 1968, Ringel, Youngs: fall 30, 35, 47, 59, och gissningen bevisades.
Formellt uttalande
Percy John Heawood förmodade 1890 att för ett givet släkte g > 0, det minsta antal färger som krävs för att färga alla grafer som ritas på en orienterbar yta av det släktet (eller motsvarande för att färga regionerna av en uppdelning av ytan i enkelt sammankopplade områden ) ges av
där är golvfunktionen .
Genom att ersätta släktet med Euler-karaktäristiken får vi en formel som täcker både de orienterbara och icke-orienterbara fallen,
Detta förhållande gäller, som Ringel och Youngs visade, för alla ytor förutom Klein-flaskan . Philip Franklin (1930) bevisade att Klein-flaskan kräver högst 6 färger, snarare än 7 enligt formeln. Franklin -grafen kan ritas på Klein-flaskan på ett sätt som bildar sex inbördes närliggande regioner, vilket visar att denna gräns är tät.
Den övre gränsen, bevisad i Heawoods ursprungliga korta papper, är baserad på en girig färgalgoritm . Genom att manipulera Euler-karakteristiken kan man visa att varje graf som är inbäddad i den givna ytan måste ha minst en vertex av grad mindre än den givna gränsen. Om man tar bort denna vertex och färgar resten av grafen, säkerställer det lilla antalet kanter som faller på den borttagna vertexen att den kan läggas tillbaka till grafen och färgläggas utan att öka det nödvändiga antalet färger bortom gränsen. Åt andra hållet är bevisningen svårare och går ut på att visa att i varje fall (förutom Klein-flaskan) kan en komplett graf med ett antal hörn lika med det givna antalet färger bäddas in på ytan.
Exempel
Torus har g = 1, så χ = 0. Därför, som formeln anger, kan varje uppdelning av torus i regioner färgas med högst sju färger . Illustrationen visar en underavdelning av torus där var och en av sju regioner ligger intill varandra; denna underavdelning visar att gränsen för sju på antalet färger är snäv för detta fall. Gränsen för denna underavdelning bildar en inbäddning av Heawood-grafen på torus.
- Franklin, P. (1934). "Ett sexfärgsproblem". MIT Journal of Mathematics and Physics . 13 (1–4): 363–379. doi : 10.1002/sapm1934131363 . hdl : 2027/mdp.39015019892200 .
- Heawood, PJ (1890). "Kartfärgsats". Quarterly Journal of Mathematics . 24 : 332-338.
- Ringel, G .; Youngs, JWT (1968). "Lösning av Heawood kartfärgningsproblem" . Proceedings of the National Academy of Sciences of the United States of America . 60 (2): 438–445. Bibcode : 1968PNAS...60..438R . doi : 10.1073/pnas.60.2.438 . MR 0228378 . PMC 225066 . PMID 16591648 .