Grötzsch's theorem (graph theory)

from Wikipedia, the free encyclopedia

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

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

Grötzsch graph: a non-planar triangle-free graph that has no 3-coloration

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