Grötzsch's theorem (graph theory)
In graph theory , a branch of mathematics that is set of Grötzsch one on Herbert Grötzsch declining rate over the colorability of graphs with three colors.
Dyeability
![](https://upload.wikimedia.org/wikipedia/commons/thumb/c/ce/Bidiakis_cube_3COL.svg/180px-Bidiakis_cube_3COL.svg.png)
A 3-coloration of the Bidiakis graph , a triangle-free planar graph
A coloring assigns a color to each node of a graph, so that the nodes of each edge are colored with different colors. One is interested in the minimum number of colors necessary to color a given graph. The four-color theorem states that any planar graph can be colored with four colors. Grötzsch's theorem answers the question which planar graphs can even be colored with three colors.
Grötzsch's theorem
A triangle-free planar graph can be colored with three colors.
(A graph is called triangle-free if it does not contain a subgraph that is isomorphic to the complete graph .)
literature
- Herbert Grötzsch: On the theory of discrete structures, VII: A three-color theorem for three-circle-free networks on the sphere , Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Series 8, 109-120 (1959).