Grötzsch-tétel

Egy háromszögmentes síkgráf, a „bidiakis cube” (LCF: [-6,4,-4]4 (wd)) 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.[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 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. [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 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.[8]

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

Jegyzetek

  1. ↑ a b (Grünbaum 1963).
  2. ↑ (Thomassen 2003)
  3. ↑ (Glebov, Kostochka & Tashkinov 2005).
  4. ↑ (Steinberg & Younger 1989)
  5. ↑ (Asghar 2012)
  6. ↑ Dvořák, Zdeněk; Kráľ, Daniel & Thomas, Robin (2009), Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies.
  7. ↑ The European Prize in Combinatorics, University of Bergen, September 2015, <https://eurocomb2015.b.uib.no/eurocomb/the-european-prize-in-combinatorics/>. Hozzáférés ideje: 2015-09-16 Archiválva 2016. augusztus 20-i dátummal a Wayback Machine-ben.
  8. ↑ (Heckman 2007).
  9. ↑ (Naserasr 2007), Theorem 11; (Nešetřil & Ossona de Mendez 2012).
  10. ↑ (Dvořák, Kawarabayashi & Thomas 2009). A problémára vonatkozó korábbi algoritmusokat lásd: (Kowalik 2010).
  • 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> Archiválva 2008. december 3-i dátummal a Wayback Machine-ben.
  • 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.
  • 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.
  • 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> Archiválva 2019. február 26-i dátummal a Wayback Machine-ben.
  • Matematika Matematikaportál • összefoglaló, színes tartalomajánló lap