“Grötzsch's theorem”的意思、由来-开放百科全书

In the mathematical field of graph theory, Grötzsch'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 Grötzsch's theorem only three colors are needed for planar graphs that do not contain three mutually-adjacent vertices.

History

The theorem is named after German mathematician Herbert Grötzsch, who published its proof in 1959.

Grötzsch's original proof was complex. {{harvtxt|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 1989, Richard Steinberg and

Dan Younger^[4] gave the first correct proof, in English, of the dual version of this theorem. In 2012, Nabiha Asghar^[5] gave a new and much simpler proof of the theorem that is inspired by Thomassen's work.

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 graph K₄, and infinitely many other planar graphs containing K₄, 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 K₄-free graphs, either: not every planar graph that requires 4 colors contains K₄. 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 K₃. In the language of homomorphisms, Grötzsch's theorem states that every triangle-free planar graph has a homomorphism to K₃.

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 K₃ 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 K₃ factor.

However, the Clebsch graph and its tensor product with K₃ 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 {{harvtxt|de Castro|Cobos|Dana|Márquez|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]

Notes

1. ^¹{{harvtxt|Grünbaum|1963}}.
2. ^{{harvtxt|Thomassen|2003}}
3. ^{{harvtxt|Glebov|Kostochka|Tashkinov|2005}}.
4. ^{{harvtxt|Steinberg|Younger|1989}}
5. ^{{harvtxt|Asghar|2012}}
6. ^{{citation | last1 = Dvořák | first1 = Zdeněk | author1-link = Zdeněk Dvořák | last2 = Kráľ | first2 = Daniel | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician) | arxiv = 0911.0885 | title = Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies | year = 2009| bibcode = 2009arXiv0911.0885D}}.
7. ^{{citation|url=https://eurocomb2015.b.uib.no/eurocomb/the-european-prize-in-combinatorics/|title=The European Prize in Combinatorics|work=EuroComb 2015|publisher=University of Bergen|date=September 2015|accessdate=2015-09-16}}.
8. ^{{harvtxt|Heckman|2007}}.
9. ^{{harvtxt|Naserasr|2007}}, Theorem 11; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}.
10. ^{{harvtxt|Dvořák|Kawarabayashi|Thomas|2009}}. For earlier work on algorithms for this problem, see {{harvtxt|Kowalik|2010}}.

History

Larger classes of graphs

Factoring through a homomorphism

Geometric representation

Computational complexity

Notes

References