Grötzsch's theorem
Encyclopedia
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. The theorem is named after German mathematician Herbert Grötzsch
, who published its proof in 1959.
Grötzsch's original proof was complex. attempted to simplify it but his proof was erroneous.
A slightly more general result is true: if a planar graph has at most three triangles then it is 3-colorable. However, the planar complete graph
K4, and infinitely many other planar graphs containing K4, contain four triangles and are not 3-colorable. 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.
A result of combines Grötzsch's theorem with Scheinerman's conjecture
on the representation of planar graphs as intersection graph
s of line segment
s. 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.
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.http://math.asu.edu/~checkman/Steinberg.html
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, Grötzsch's theorem is the statement that every triangle-free
Triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
can be colored
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
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
Herbert Grötzsch
Camillo Herbert Grötzsch was a mathematician from Halle, Germany. Grötzsch worked in graph theory. He was the discoverer and eponym of the Grötzsch graph, a triangle-free graph that requires four colors in any graph coloring, and Grötzsch's theorem, the result that every triangle-free planar graph...
, who published its proof in 1959.
Grötzsch's original proof was complex. attempted to simplify it but his proof was erroneous.
A slightly more general result is true: if a planar graph has at most three triangles then it is 3-colorable. However, the planar complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
K4, and infinitely many other planar graphs containing K4, contain four triangles and are not 3-colorable. 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.
A result of combines Grötzsch's theorem with Scheinerman's conjecture
Scheinerman's conjecture
In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis , following earlier results that every planar graph could be represented...
on the representation of planar graphs as intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
s of line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s. 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.
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
Grötzsch graph
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, and chromatic number 4. It is named after German mathematician Herbert Grötzsch, and its existence demonstrates that the assumption of planarity is necessary in Grötzsch's theorem ...
and the Chvátal graph
Chvátal graph
In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by .It is triangle-free: its girth is four. It is 4-regular: each vertex has exactly four neighbors. And its chromatic number is 4: it can be colored using four colors, but...
are triangle-free graphs requiring four colors, and the Mycielskian
Mycielskian
In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph G is a graph μ formed from G by a construction of , who used it to show that there exist triangle-free graphs with arbitrarily large chromatic number.-Construction:Let the n vertices of the given...
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.http://math.asu.edu/~checkman/Steinberg.html