Grötzsch-tétel
A matematika, azon belül a gráfelmélet területén a Grötzsch-tétel az az állítás, ami szerint bármely háromszögmentes síkgráf kiszínezhető mindössze három szín segítségével. A négyszíntétel garantálja, hogy az élek metszése nélkül síkba lerajzolható gráfok csúcsai legfeljebb négy különböző színnel kiszínezhetők úgy, hogy egyik csúcsnak se legyen vele azonos színű szomszédja – a Grötzsch-tétel szerint olyan síkgráfnál, mely nem tartalmaz egymással kölcsönösen szomszédos három csúcsot, erre három szín is elegendő.

Története
A tétel az 1959-ben azt kimondó és bizonyító Herbert Grötzsch német matematikusról kapta nevét. Grötzsch eredeti bizonyítása meglehetősen bonyolult volt.  megkísérelte leegyszerűsíteni, de bizonyításába hibák csúsztak.

2003-ban Carsten Thomassen egy kapcsolódó tételből kísérelt meg alternatív bizonyítást nyerni: bármely legalább 5 derékbőségű síkgráf 3-listaszínezhető. A Grötzsch-tétel azonban nem terjed ki a listaszínezésre: léteznek olyan háromszögmentes síkgráfok, melyek nem 3-listaszínezhetők. 1989-ben Richard Steinberg és Dan Younger adták meg az első korrekt bizonyítást a tétel duálisára. 2012-ben Thomassen munkája nyomán Nabiha Asghar adta meg a tétel új és sokkal egyszerűbb bizonyítását.

Gráfok nagyobb osztályára érvényes
A tételnél némileg általánosabb állítás is igazolható: ha egy síkgráfban legfeljebb három háromszög van, akkor 3-színezhető. A K4 teljes gráf azonban síkba rajzolható, és ez a gráf, valamint végtelen sok a K4-et tartalmazó síkgráf már négy háromszöget tartalmaz és nem 3-színezhető. 2009-ben, Dvořák, Kráľ és Thomas bejelentették a bizonyítását egy még 1969-ben L. Havel által megsejtett általánosításnak: létezik olyan d konstans, amire ha egy síkgráf két háromszöge között mindig legalább d a távolság, akkor a síkgráf 3-színezhető. A konstans pontos értéke nem ismert, de 3-nál biztosan nagyobb.  Ez a munka alapozta meg Dvořák 2015-ös Európai Kombinatorikai Díját.

A tétel nem általánosítható síkba nem rajzolható háromszögmentes gráfokra: nem mindegyik ilyen gráf 3-színezhető. Az ismertebbek közül a Grötzsch-gráf és a Chvátal-gráf színezéséhez négy színre van szükség, és a Mycielski-konstrukció segítségével tetszőlegesen magas kromatikus számú háromszögmentes gráfok szerkeszthetők.

A tétel nem általánosítható az összes K4-mentes síkgráfra sem: nem minden 4 színt igénylő síkgráf tartalmazza a K4-et. Sőt, létezik 4 hosszúságú kört nem tartalmazó síkgráf, amit nem lehet 3-színezni.

Faktorizálás homomorfizmussal
Egy G gráf 3-színezése leírható úgy is, mint a G-ből a K3-ba irányuló gráfhomomorfizmus. A homomorfizmusok nyelvén megfogalmazva a Grötzsch-tétel kimondja, hogy minden háromszögmentes síkgráfhoz tartozik azt a K3-ba átvivő homomorfizmus. Naserasr megmutatta, hogy minden háromszögmentes síkgráfnak létezik homomorfizmusa, ami a 4-kromatikus Clebsch-gráfba viszi át. A két eredmény összevonásával megmutatható, hogy minden háromszögmentes síkgráfnak van homomorfizmusa egy háromszögmentes 3-színezhető gráffal, méghozzá a K3 és a Clebsch-gráf kategóriai (tenzor) szorzata.
Ekkor a gráf színezése visszanyerhető ennek a homomorfizmusnak és a kategóriai szorzat és a K3 faktorral való homomorfizmusnak a függvénykompozíciójával.
Mivel azonban sem a Clebsch-gráf, sem annak K3-mal való kategóriai szorzata nem síkba rajzolható, nem létezik olyan háromszögmentes síkgráf, amibe minden más háromszögmentes síkgráf homomorfizmussal átvihető.

Geometriai ábrázolás
 eredménye összegzi Grötzsch tételét a Scheinerman-tétellel, miszerint a síkgráfok reprezentálhatók egyenesszakaszok metszetgráfjaként. Sikerült bizonyítaniuk, hogy minden háromszögmentes síkgráf reprezentálható legfeljebb három különböző irányú egyenesszakaszokkal oly módon, hogy a gráf két csúcsa pontosan akkor szomszédos, ha az őket reprezentálható egyenesszakaszok metszik egymást. A gráf 3-színezése megkapható úgy, hogy két csúcsot akkor színezünk egyformára, ha a hozzájuk tartozó szakaszok ugyanolyan irányultságúak.

Számítási bonyolultság
Adott háromszögmentes síkgráf 3-színezése lineáris időben megtalálható.

Fordítás

Jegyzetek

.
.
.
.
.
.
.
.
.
.
.
 .

Gráfok színezése
Síkgráfok
Gráfelméleti tételek
A matematika , azon belül a gráfelmélet területén a Grötzsch-tétel az az állítás , ami szerint bármely háromszögmentes síkgráf kiszínezhető mindössze három szín segítségével . A négyszíntétel garantálja , hogy az élek metszése nélkül síkba lerajzolható gráfok csúcsai legfeljebb négy különböző színnel kiszínezhetők úgy , hogy egyik csúcsnak se legyen vele azonos színű szomszédja – a Grötzsch-tétel szerint olyan síkgráfnál , mely nem tartalmaz egymással kölcsönösen szomszédos három csúcsot , erre három szín is elegendő . Története A tétel azben azt kimondó és bizonyító Herbert Grötzsch német matematikusról kapta nevét . Grötzsch eredeti bizonyítása meglehetősen bonyolult volt. megkísérelte leegyszerűsíteni , de bizonyításába hibák csúsztak . 2003-ban Carsten Thomassen egy kapcsolódó tételből kísérelt meg alternatív bizonyítást nyerni : bármely legalábbderékbőségű síkgráflistaszínezhető . A Grötzsch-tétel azonban nem terjed ki a listaszínezésre : léteznek olyan háromszögmentes síkgráfok , melyek nemlistaszínezhetők.ben Richard Steinberg és Dan Younger adták meg az első korrekt bizonyítást a tétel duálisára.ben Thomassen munkája nyomán Nabiha Asghar adta meg a tétel új és sokkal egyszerűbb bizonyítását . Gráfok nagyobb osztályára érvényes A tételnél némileg általánosabb állítás is igazolható : ha egy síkgráfban legfeljebb három háromszög van , akkorszínezhető . A K4 teljes gráf azonban síkba rajzolható , és ez a gráf , valamint végtelen sok a K4-et tartalmazó síkgráf már négy háromszöget tartalmaz és nemszínezhető.ben , Dvořák , Kráľ és Thomas bejelentették a bizonyítását egy mégben L. Havel által megsejtett általánosításnak : létezik olyan d konstans , amire ha egy síkgráf két háromszöge között mindig legalább d a távolság , akkor a síkgráfszínezhető . A konstans pontos értéke nem ismert , denál biztosan nagyobb . Ez a munka alapozta meg Dvořákös Európai Kombinatorikai Díját . A tétel nem általánosítható síkba nem rajzolható háromszögmentes gráfokra : nem mindegyik ilyen gráfszínezhető . Az ismertebbek közül a Grötzsch-gráf és a Chvátal-gráf színezéséhez négy színre van szükség , és a Mycielski-konstrukció segítségével tetszőlegesen magas kromatikus számú háromszögmentes gráfok szerkeszthetők . A tétel nem általánosítható az összes K4-mentes síkgráfra sem : nem mindenszínt igénylő síkgráf tartalmazza a K4-et . Sőt , létezikhosszúságú kört nem tartalmazó síkgráf , amit nem lehetszínezni . Faktorizálás homomorfizmussal Egy G gráfszínezése leírható úgy is , mint a G-ből a K3-ba irányuló gráfhomomorfizmus . A homomorfizmusok nyelvén megfogalmazva a Grötzsch-tétel kimondja , hogy minden háromszögmentes síkgráfhoz tartozik azt a K3-ba átvivő homomorfizmus . Naserasr megmutatta , hogy minden háromszögmentes síkgráfnak létezik homomorfizmusa , ami akromatikus Clebsch-gráfba viszi át . A két eredmény összevonásával megmutatható , hogy minden háromszögmentes síkgráfnak van homomorfizmusa egy háromszögmentesszínezhető gráffal , méghozzá a K3 és a Clebsch-gráf kategóriai ( tenzor ) szorzata . Ekkor a gráf színezése visszanyerhető ennek a homomorfizmusnak és a kategóriai szorzat és a K3 faktorral való homomorfizmusnak a függvénykompozíciójával . Mivel azonban sem a Clebsch-gráf , sem annak K3-mal való kategóriai szorzata nem síkba rajzolható , nem létezik olyan háromszögmentes síkgráf , amibe minden más háromszögmentes síkgráf homomorfizmussal átvihető . Geometriai ábrázolás eredménye összegzi Grötzsch tételét a Scheinerman-tétellel , miszerint a síkgráfok reprezentálhatók egyenesszakaszok metszetgráfjaként . Sikerült bizonyítaniuk , hogy minden háromszögmentes síkgráf reprezentálható legfeljebb három különböző irányú egyenesszakaszokkal oly módon , hogy a gráf két csúcsa pontosan akkor szomszédos , ha az őket reprezentálható egyenesszakaszok metszik egymást . A gráfszínezése megkapható úgy , hogy két csúcsot akkor színezünk egyformára , ha a hozzájuk tartozó szakaszok ugyanolyan irányultságúak . Számítási bonyolultság Adott háromszögmentes síkgráfszínezése lineáris időben megtalálható . Fordítás Jegyzetek . . . . . . . . . . . \ . Gráfok színezése Síkgráfok Gráfelméleti tételek