Grötschin lause on väite, että mikä tahansa kolmioton tasograafi voidaan värjätä kolmella värillä. Neljän värin teoreeman mukaan minkä tahansa graafin, joka voidaan piirtää tasoon ilman reunoja ylittämättä, kärjet voidaan värjätä korkeintaan neljällä eri värillä siten, että minkä tahansa reunan kaksi päätä ovat erivärisiä. Grötzschin lauseen mukaan tasograafille, joka ei sisällä kolmea toisiinsa liittyvää kärkeä, riittää vain kolme väriä.
Lause on nimetty saksalaisen matemaatikon Herbert Grötschin mukaan, joka julkaisi todisteen vuonna 1959. Grötschin alkuperäinen todistus oli monimutkainen. Berge [1] yritti yksinkertaistaa sitä, mutta hänen todistuksensa sisälsi virheitä [2] .
Vuonna 2003 Carsten Thomassen [3] antoi vaihtoehtoisen todisteen, alkaen siihen liittyvästä lauseesta – jokaisella tasograafilla, jonka ympärysmitta on vähintään viisi, on määrätty 3-väri . Grötzschin lause itsessään ei kuitenkaan ulotu värjäyksestä määrättyyn värjäykseen - on kolmiota sisältämättömiä tasokaavioita, joilla ei ole määrättyä kolmiväristä väritystä [4] . Vuonna 1989 Richard Steinberg ja Dan Junger [5] antoivat ensimmäisen oikean englanninkielisen todisteen tämän lauseen kaksoisversiosta. Vuonna 2012 Nabiha Asghar [6] antoi lauseelle uuden ja paljon yksinkertaisemman todisteen Thomassenin työn innoittamana.
Hieman yleisempi tulos pitää paikkansa: jos tasograafissa on enintään kolme kolmiota, se on väritettävissä kolmella värillä [2] . Kuitenkin tasomainen täydellinen graafi K 4 ja äärettömän monet muut tasograafit, jotka sisältävät K 4 :n, sisältävät neljä kolmiota eivätkä ole 3-värillisiä. Vuonna 2009 Dvorak, Kralj ja Thomas ilmoittivat todisteen toisesta yleistyksestä, jota L. Havelin arvelu ehdotti vuonna 1969: on olemassa sellainen vakio d , että jos tasograafissa on kaksi kolmiota, joiden etäisyys on enintään d , niin kaavio voidaan värittää kolmella värillä [7] . Tämä työ oli osa vuoden 2015 Euroopan Dvorak Combinatorics -palkinnon perustaa [8]
Lause ei ole yleistettävissä kaikkiin epätasoisiin graafisiin ilman kolmioita - jokainen ei-tasoinen kuvaaja ilman kolmioita ei ole 3-väritettävä. Erityisesti Grötzsch- ja Chwátala -graafit ovat kolmiovapaita graafisia, mutta vaativat neljä väriä, ja Mycelskian on graafimuunnos, jonka avulla voidaan rakentaa kolmiottomia graafisia, jotka vaativat mielivaltaisen suuren määrän värejä.
Lause ei myöskään ole yleistettävissä kaikille tasomaisille K 4 -vapaille graafeille – jokainen tasograafi, joka vaatii 4 väriä, ei sisällä K 4 :ää . Erityisesti on olemassa tasograafi ilman 4-sykliä, joka ei voi olla 3-värinen [9] .
Graafin G 3-värinen väritys voidaan kuvata graafin homomorfismilla G : stä kolmioon K 3 . Homomorfismien kielellä Grötzschin lause sanoo, että millä tahansa kolmiottomalla tasograafilla on homomorfismi graafin K 3 kanssa . Nasserasr osoitti, että millä tahansa kolmiottomalla tasograafilla on myös homomorfismi Clebschin graafiin , 4-kromaattiseen graafiin. Yhdistämällä nämä kaksi tulosta voidaan osoittaa, että millä tahansa kolmiovapaalla tasograafilla on homomorfismi kolmiottomaan kolmiväriseen graafiin, K 3 -tensorituloon Clebsch-graafin kanssa. Graafin väritys voidaan sitten saada päällekkäin tämä homomorfismi niiden tensoritulon homomorfismin kanssa niiden K3 - tekijään. Clebsch-graafi ja sen tensoritulo K 3 :n kanssa eivät kuitenkaan ole tasomaisia. Ei ole olemassa kolmiotonta tasograafia, johon mikä tahansa kolmioton tasograafi voidaan kuvata homomorfismilla [10] [11] .
Castron, Cobosin, Danin, Marquezin [12] tulos yhdistää Grötzschin lauseen Scheinermanin oletukseen tasograafien esityksistä segmenttien leikkauskaavioina . He osoittivat, että mikä tahansa kolmioton tasograafi voidaan esittää joukolla viivaosia, joissa on kolme mahdollista kaltevuutta, niin että kaksi graafin kärkeä ovat vierekkäin silloin ja vain, jos edustavat janat leikkaavat toisiaan. Graafin kolmivärinen väritys voidaan sitten saada antamalla kahdelle kärjelle sama väri, jos niiden janoilla on sama kaltevuus.
Kun on annettu tasomainen kolmiovapaa graafi, graafista voidaan saada 3-väritys lineaarisessa ajassa [13] .