In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-freeplanar graph can be colored with only three colors. According to the four-color theorem, every graph that can be drawn in the plane without edge crossings can have its vertices colored using at most four different colors, so that the two endpoints of every edge have different colors, but according to Grötzsch's theorem only three colors are needed for planar graphs that do not contain three mutually adjacent vertices.
The theorem is named after German mathematician Herbert Grötzsch, who published its proof in 1959. Grötzsch's original proof was complex. Berge (1960) attempted to simplify it but his proof was erroneous.[1]
In 2003, Carsten Thomassen[2] derived an alternative proof from another related theorem: every planar graph with girth at least five is 3-list-colorable. However, Grötzsch's theorem itself does not extend from coloring to list coloring: there exist triangle-free planar graphs that are not 3-list-colorable.[3] In 2012, Nabiha Asghar[4] gave a new and much simpler proof of the theorem that is inspired by Thomassen's work.
In 1989, Richard Steinberg and Dan Younger[5] gave the first correct proof, in English, of the dual version of this theorem.
Larger classes of graphs
A slightly more general result is true: if a planar graph has at most three triangles then it is 3-colorable.[1] However, the planar complete graphK4, and infinitely many other planar graphs containing K4, contain four triangles and are not 3-colorable. In 2009, Dvořák, Kráľ, and Thomas announced a proof of another generalization, conjectured in 1969 by L. Havel: there exists a constant d such that, if a planar graph has no two triangles within distance d of each other, then it can be colored with three colors.[6] This work formed part of the basis for Dvořák's 2015 European Prize in Combinatorics.[7]
The theorem cannot be generalized to all nonplanar triangle-free graphs: not every nonplanar triangle-free graph is 3-colorable. In particular, the Grötzsch graph and the Chvátal graph are triangle-free graphs requiring four colors, and the Mycielskian is a transformation of graphs that can be used to construct triangle-free graphs that require arbitrarily high numbers of colors.
The theorem cannot be generalized to all planar K4-free graphs, either: not every planar graph that requires 4 colors contains K4. In particular, there exists a planar graph without 4-cycles that cannot be 3-colored.[8]
Factoring through a homomorphism
A 3-coloring of a graph G may be described by a graph homomorphism from G to a triangle K3. In the language of homomorphisms, Grötzsch's theorem states that every triangle-free planar graph has a homomorphism to K3. Naserasr showed that every triangle-free planar graph also has a homomorphism to the Clebsch graph, a 4-chromatic graph. By combining these two results, it may be shown that every triangle-free planar graph has a homomorphism to a triangle-free 3-colorable graph, the tensor product of K3 with the Clebsch graph. The coloring of the graph may then be recovered by composing this homomorphism with the homomorphism from this tensor product to its K3 factor. However, the Clebsch graph and its tensor product with K3 are both non-planar; there does not exist a triangle-free planar graph to which every other triangle-free planar graph may be mapped by a homomorphism.[9]
Geometric representation
A result of de Castro et al. (2002) combines Grötzsch's theorem with Scheinerman's conjecture on the representation of planar graphs as intersection graphs of line segments. They proved that every triangle-free planar graph can be represented by a collection of line segments, with three slopes, such that two vertices of the graph are adjacent if and only if the line segments representing them cross. A 3-coloring of the graph may then be obtained by assigning two vertices the same color whenever their line segments have the same slope.
Computational complexity
Given a triangle-free planar graph, a 3-coloring of the graph can be found in linear time.[10]
Asghar, Nabiha (2012), "Grötzsch's Theorem" (PDF), Master's Thesis, University of Waterloo, doi:10.13140/RG.2.1.1326.9367.
Berge, Claude (1960), "Les problèmes de colaration en théorie des graphs", Publ. Inst. Statist. Univ. Paris, 9: 123–160. As cited by Grünbaum (1963).{{citation}}: CS1 maint: postscript (link)
de Castro, N.; Cobos, F. J.; Dana, J. C.; Márquez, A. (2002), "Triangle-free planar graphs as segment intersection graphs" (PDF), Journal of Graph Algorithms and Applications, 6 (1): 7–26, doi:10.7155/jgaa.00043, MR 1898201.
Dvořák, Zdeněk; Kawarabayashi, Ken-ichi; Thomas, Robin (2009), "Three-coloring triangle-free planar graphs in linear time", (PDF), pp. 1176–1182, arXiv:1302.5121, Bibcode:2013arXiv1302.5121D, archived from the original (PDF) on 2012-10-18, retrieved 2013-02-22.
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, MR 0116320.
Grünbaum, Branko (1963), "Grötzsch's theorem on 3-colorings", Michigan Math. J., 10 (3): 303–310, doi:10.1307/mmj/1028998916, MR 0154274.
Heckman, Christopher Carl (2007), , archived from the original on 2012-07-22, retrieved 2012-07-27.
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.
January 07, 2023
grötzsch, theorem, mathematical, field, graph, theory, statement, that, every, triangle, free, planar, graph, colored, with, only, three, colors, according, four, color, theorem, every, graph, that, drawn, plane, without, edge, crossings, have, vertices, color. In the mathematical field of graph theory Grotzsch s theorem is the statement that every triangle free planar graph can be colored with only three colors According to the four color theorem every graph that can be drawn in the plane without edge crossings can have its vertices colored using at most four different colors so that the two endpoints of every edge have different colors but according to Grotzsch s theorem only three colors are needed for planar graphs that do not contain three mutually adjacent vertices A 3 coloring of a triangle free planar graph Contents 1 History 2 Larger classes of graphs 3 Factoring through a homomorphism 4 Geometric representation 5 Computational complexity 6 Notes 7 ReferencesHistory EditThe theorem is named after German mathematician Herbert Grotzsch who published its proof in 1959 Grotzsch s original proof was complex Berge 1960 attempted to simplify it but his proof was erroneous 1 In 2003 Carsten Thomassen 2 derived an alternative proof from another related theorem every planar graph with girth at least five is 3 list colorable However Grotzsch s theorem itself does not extend from coloring to list coloring there exist triangle free planar graphs that are not 3 list colorable 3 In 2012 Nabiha Asghar 4 gave a new and much simpler proof of the theorem that is inspired by Thomassen s work In 1989 Richard Steinberg and Dan Younger 5 gave the first correct proof in English of the dual version of this theorem Larger classes of graphs EditA slightly more general result is true if a planar graph has at most three triangles then it is 3 colorable 1 However the planar complete graph K4 and infinitely many other planar graphs containing K4 contain four triangles and are not 3 colorable In 2009 Dvorak Kraľ and Thomas announced a proof of another generalization conjectured in 1969 by L Havel there exists a constant d such that if a planar graph has no two triangles within distance d of each other then it can be colored with three colors 6 This work formed part of the basis for Dvorak s 2015 European Prize in Combinatorics 7 The theorem cannot be generalized to all nonplanar triangle free graphs not every nonplanar triangle free graph is 3 colorable In particular the Grotzsch graph and the Chvatal graph are triangle free graphs requiring four colors and the Mycielskian is a transformation of graphs that can be used to construct triangle free graphs that require arbitrarily high numbers of colors The theorem cannot be generalized to all planar K4 free graphs either not every planar graph that requires 4 colors contains K4 In particular there exists a planar graph without 4 cycles that cannot be 3 colored 8 Factoring through a homomorphism EditA 3 coloring of a graph G may be described by a graph homomorphism from G to a triangle K3 In the language of homomorphisms Grotzsch s theorem states that every triangle free planar graph has a homomorphism to K3 Naserasr showed that every triangle free planar graph also has a homomorphism to the Clebsch graph a 4 chromatic graph By combining these two results it may be shown that every triangle free planar graph has a homomorphism to a triangle free 3 colorable graph the tensor product of K3 with the Clebsch graph The coloring of the graph may then be recovered by composing this homomorphism with the homomorphism from this tensor product to its K3 factor However the Clebsch graph and its tensor product with K3 are both non planar there does not exist a triangle free planar graph to which every other triangle free planar graph may be mapped by a homomorphism 9 Geometric representation EditA result of de Castro et al 2002 combines Grotzsch s theorem with Scheinerman s conjecture on the representation of planar graphs as intersection graphs of line segments They proved that every triangle free planar graph can be represented by a collection of line segments with three slopes such that two vertices of the graph are adjacent if and only if the line segments representing them cross A 3 coloring of the graph may then be obtained by assigning two vertices the same color whenever their line segments have the same slope Computational complexity EditGiven a triangle free planar graph a 3 coloring of the graph can be found in linear time 10 Notes Edit a b Grunbaum 1963 Thomassen 2003 Glebov Kostochka amp Tashkinov 2005 Asghar 2012 Steinberg amp Younger 1989 Dvorak Zdenek Kraľ Daniel Thomas Robin 2009 Three coloring triangle free graphs on surfaces V Coloring planar graphs with distant anomalies arXiv 0911 0885 Bibcode 2009arXiv0911 0885D The European Prize in Combinatorics EuroComb 2015 University of Bergen September 2015 retrieved 2015 09 16 Heckman 2007 Naserasr 2007 Theorem 11 Nesetril amp Ossona de Mendez 2012 Dvorak Kawarabayashi amp Thomas 2009 For earlier work on algorithms for this problem see Kowalik 2010 References EditAsghar Nabiha 2012 Grotzsch s Theorem PDF Master s Thesis University of Waterloo doi 10 13140 RG 2 1 1326 9367 Berge Claude 1960 Les problemes de colaration en theorie des graphs Publ Inst Statist Univ Paris 9 123 160 As cited by Grunbaum 1963 a href Template Citation html title Template Citation citation a CS1 maint postscript link de Castro N Cobos F J Dana J C Marquez A 2002 Triangle free planar graphs as segment intersection graphs PDF Journal of Graph Algorithms and Applications 6 1 7 26 doi 10 7155 jgaa 00043 MR 1898201 Dvorak Zdenek Kawarabayashi Ken ichi Thomas Robin 2009 Three coloring triangle free planar graphs in linear time Proc 20th ACM SIAM Symposium on Discrete Algorithms PDF pp 1176 1182 arXiv 1302 5121 Bibcode 2013arXiv1302 5121D archived from the original PDF on 2012 10 18 retrieved 2013 02 22 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 Grotzsch s Theorem for the projective plane Ars Combinatoria 28 15 31 Grotzsch Herbert 1959 Zur Theorie der diskreten Gebilde VII Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel Wiss Z Martin Luther U Halle Wittenberg Math Nat Reihe 8 109 120 MR 0116320 Grunbaum Branko 1963 Grotzsch s theorem on 3 colorings Michigan Math J 10 3 303 310 doi 10 1307 mmj 1028998916 MR 0154274 Heckman Christopher Carl 2007 Progress on Steinberg s Conjecture archived from the original on 2012 07 22 retrieved 2012 07 27 Kowalik Lukasz 2010 Fast 3 coloring triangle free planar graphs PDF Algorithmica 58 3 770 789 doi 10 1007 s00453 009 9295 2 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 MR 2305893 Nesetril Jaroslav Ossona de Mendez Patrice 2012 2 5 Homomorphism Dualities Sparsity Algorithms and Combinatorics vol 28 Heidelberg Springer pp 15 16 doi 10 1007 978 3 642 27875 4 hdl 10338 dmlcz 143192 ISBN 978 3 642 27874 7 MR 2920058 Thomassen Carsten 2003 A short list color proof of Grotzsch s theorem Journal of Combinatorial Theory Series B 88 1 189 192 doi 10 1016 S0095 8956 03 00029 7 Retrieved from https en wikipedia org w index php title Grotzsch 27s theorem amp oldid 1102266361, wikipedia, wiki, book, books, library,
