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ő., Theorem 11; .

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ó.. A problémára vonatkozó korábbi algoritmusokat lásd: .

Fordítás

Jegyzetek

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

Kategória:Gráfok színezése Kategória:Síkgráfok Kategória:Gráfelméleti tételek