Grötzschs sats - Grötzsch's theorem

En trefärgning av en triangelfri plan graf

I matematiska området grafteori , Grötzsch teorem är påståendet att varje triangel fria plana graf kan färgas med endast tre färger. Enligt fyrfärgssatsen kan varje graf som kan ritas i planet utan kantkorsningar ha sina hörn färgade med högst fyra olika färger, så att de två ändpunkterna för varje kant har olika färger, men enligt Grötzschs sats bara tre färger behövs för plana grafer som inte innehåller tre intilliggande hörn.

Historia

Satsen är uppkallad efter den tyska matematikern Herbert Grötzsch , som publicerade sitt bevis 1959. Grötzschs ursprungliga bevis var komplicerat. Berge (1960) försökte förenkla det men hans bevis var felaktigt.

År 2003 härledde Carsten Thomassen ett alternativt bevis från en annan relaterad teorem: varje plan graf med minst fem omkrets är 3-lista-färgbar . Grötzschs sats sträcker sig dock inte från färgning till listfärgning: det finns triangelfria plana grafer som inte är 3-lista-färgbara. 2012 gav Nabiha Asghar ett nytt och mycket enklare bevis på satsen som är inspirerad av Thomassens arbete.

1989 gav Richard Steinberg och Dan Younger det första korrekta beviset på engelska av den dubbla versionen av denna sats.

Större klasser av diagram

Ett något mer allmänt resultat är sant: om en plan graf har högst tre trianglar är den 3-färgbar. Emellertid, den plana komplett graf K 4 , och oändligt många andra plana grafer innehållande K 4 , innehåller fyra trianglar och är inte 3-PLAUSIBEL. 2009 tillkännagav Dvořák , Kráľ och Thomas ett bevis på en annan generalisering, antagen 1969 av L. Havel: det finns en konstant d sådan att, om en plan graf inte har två trianglar inom avstånd d från varandra, då kan den vara färgade med tre färger. Detta arbete utgjorde en del av grunden för Dvořáks europeiska pris 2015 i kombinatorik .

Satsen kan inte generaliseras till alla icke-plana triangelfria grafer: inte alla icke-plana triangelfria diagram är 3-färgbara. I synnerhet är Grötzsch-grafen och Chvátal-grafen triangelfria grafer som kräver fyra färger, och Mycielskian är en omvandling av grafer som kan användas för att konstruera triangelfria grafer som kräver godtyckligt höga färger.

Satsen kan inte generaliseras till alla plan K 4 -fria grafer, antingen inte varje plan kurva som kräver 4 färger innehåller K 4 . I synnerhet finns det en plan graf utan 4-cykler som inte kan vara trefärgade.

Faktorisering genom en homomorfism

En 3-färgning av en graf G kan beskrivas med en grafhomomorfi från G till en triangel K 3 . På homomorfismens språk säger Grötzschs sats att varje triangelfri plan graf har en homomorfism till K 3 . Naserasr visade att varje triangelfri plan graf också har en homomorfism till Clebsch-grafen , en 4-kromatisk graf. Genom att kombinera dessa två resultat kan det visas att varje triangelfri plan graf har en homomorfism till en triangelfri 3-färgbar graf, tensorprodukten av K 3 med Clebsch-grafen. Färgning av grafen kan sedan utvinnas genom att komponera denna homomorfism med homomorfism från denna tensor produkt till dess K 3 faktor. Emellertid Clebsch grafen och dess tensorprodukt med K 3 är båda icke-plana; det finns inte ett triangelfritt plandiagram till vilket alla andra triangelfria plana diagram kan kartläggas av en homomorfism.

Geometrisk representation

Ett resultat av de Castro et al. (2002) kombinerar Grötzschs teorem med Scheinermans antagande om framställning av plana grafer som skärningsdiagram över linjesegment . De bevisade att varje triangelfri plan graf kan representeras av en samling linjesegment med tre lutningar, så att två hörn i diagrammet ligger intill om och endast om linjesegmenten som representerar dem korsar. En trefärgning av diagrammet kan sedan erhållas genom att tilldela två hörn i samma färg när deras linjesegment har samma lutning.

Beräkningskomplexitet

Med en triangelfri plan graf kan en trefärgning av grafen hittas linjärt .

Anteckningar

Referenser