PROFILPELAJAR.COM

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. (Berge 1960) megkísérelte leegyszerűsíteni, de bizonyításába hibák csúsztak.^[1]

2003-ban Carsten Thomassen^[2] 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.^[3] 1989-ben Richard Steinberg és Dan Younger^[4] adták meg az első korrekt bizonyítást a tétel duálisára. 2012-ben Thomassen munkája nyomán Nabiha Asghar^[5] 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ő.^[1] A K₄ teljes gráf azonban síkba rajzolható, és ez a gráf, valamint végtelen sok a K₄-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. ^[6] Ez a munka alapozta meg Dvořák 2015-ös Európai Kombinatorikai Díját.^[7]

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 K₄-mentes síkgráfra sem: nem minden 4 színt igénylő síkgráf tartalmazza a K₄-et. Sőt, létezik 4 hosszúságú kört nem tartalmazó síkgráf, amit nem lehet 3-színezni.^[8]

Faktorizálás homomorfizmussal

Egy G gráf 3-színezése leírható úgy is, mint a G-ből a K₃-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 K₃-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 K₃ é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 K₃ faktorral való homomorfizmusnak a függvénykompozíciójával. Mivel azonban sem a Clebsch-gráf, sem annak K₃-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ő.^[9]

Geometriai ábrázolás

(de Castro et al. 2002) 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ó.^[10]

Fordítás

Ez a szócikk részben vagy egészben a Grötzsch's theorem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.