Grötzsch-tétel

Egy háromszögmentes síkgráf, a „bidiakis cube” (LCF: [-6,4,-4]⁴ ) 3-színezése.

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.

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 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. 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 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.

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ő.

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ó.

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.

Jegyzetek

• Berge, Claude (1960), "Les problèmes de colaration en théorie des graphs", Publ. Inst. Statist. Univ. Paris 9: 123–160
• de Castro, N.; Cobos, F. J. & Dana, J. C. et al. (2002), "Triangle-free planar graphs as segment intersection graphs", Journal of Graph Algorithms and Applications 6 (1): 7–26, doi:10.7155/jgaa.00043, <http://www.cs.brown.edu/publications/jgaa/accepted/2002/deCastro+2002.6.1.pdf>.
• Dvořák, Zdeněk; Kawarabayashi, Ken-ichi & Thomas, Robin (2009), "Three-coloring triangle-free planar graphs in linear time", Proc. 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 1176–1182, <http://www.siam.org/proceedings/soda/2009/SODA09_127_dvorakz.pdf>. Hozzáférés ideje: 2016-10-07 Archiválva 2012. október 18-i dátummal a Wayback Machine-ben.
• Glebov, A. N.; Kostochka, A. V. & Tashkinov, V. A. (2005), "Smaller planar triangle-free graphs that are not 3-list-colorable", Discrete Mathematics 290 (2–3): 269–274, DOI 10.1016/j.disc.2004.10.015.
• Steinberg, Richard & Younger, D. H. (1989), "Grötzsch's Theorem for the projective plane", Ars Combinatoria 28: 15–31.
• Grötzsch, Herbert (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8: 109–120.
• Grünbaum, Branko (1963), "Grötzsch's theorem on 3-colorings", Michigan Math. J. 10 (3): 303–310, DOI 10.1307/mmj/1028998916.
• Heckman, Christopher Carl (2007), Progress on Steinberg's Conjecture, <http://math.la.asu.edu/~checkman/Steinberg.html>. Hozzáférés ideje: 2012-07-27 Archiválva 2012. július 22-i dátummal a Wayback Machine-ben.
• Kowalik, Łukasz (2010), "Fast 3-coloring triangle-free planar graphs", Algorithmica 58 (3): 770–789, doi:10.1007/s00453-009-9295-2, <http://www.mimuw.edu.pl/~kowalik/papers/grotzsch-full.pdf>.
• Naserasr, Reza (2007), "Homomorphisms and edge-colourings of planar graphs", Journal of Combinatorial Theory, Series B 97 (3): 394–400, DOI 10.1016/j.jctb.2006.07.001.
• Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), "2.5 Homomorphism Dualities", Sparsity, vol. 28, Algorithms and Combinatorics, Heidelberg: Springer, pp. 15–16, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.
• Thomassen, Carsten (2003), "A short list color proof of Grötzsch's theorem", Journal of Combinatorial Theory, Series B 88 (1): 189–192, DOI 10.1016/S0095-8956(03)00029-7.
• Asghar, Nabiha (2012), "Grötzsch's Theorem", Master's Thesis, University of Waterloo, doi:10.13140/RG.2.1.1326.9367, <http://cs.uwaterloo.ca/~nasghar/MastersThesis.pdf>.