Grötzsch graph

From Wikipedia, the free encyclopedia
Grötzsch graph
Named after Herbert Grötzsch
Vertices 11
Edges 20
Radius 2
Diameter 2
Girth 4
Automorphisms 10 (D5)
Chromatic number 4
Chromatic index 5
Properties Hamiltonian
Triangle-free

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. 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 (Grötzsch 1959) that every triangle-free planar graph is 3-colorable. The Grötzsch graph is a member of an infinite sequence of triangle-free graphs, each the Mycielskian of the previous graph in the sequence, starting from the null graph; this sequence of graphs was used by Mycielski (1955) to show that there exist triangle-free graphs with arbitrarily large chromatic number. Therefore, the Grötzsch graph is sometimes also called the Mycielski graph or the Mycielski–Grötzsch graph. Unlike later graphs in this sequence, the Grötzsch graph is the smallest triangle-free graph with its chromatic number (Chvátal 1974).

Häggkvist (1981) used a modified version of the Grötzsch graph to disprove a conjecture of Paul Erdős and Miklos Simonovits (1973) on the chromatic number of triangle-free graphs with high degree. Häggkvist's modification consists of replacing each of the five degree-four vertices of the Grötzsch graph by a set of three vertices, replacing each of the five degree-three vertices of the Grötzsch graph by a set of two vertices, and replacing the remaining degree-five vertex of the Grötzsch graph by a set of four vertices. Two vertices in this expanded graph are connected by an edge if they correspond to vertices connected by an edge in the Grötzsch graph. The result of Häggkvist's construction is a 10-regular triangle-free graph with 29 vertices and chromatic number 4, disproving the conjecture that there is no 4-chromatic triangle-free n-vertex graph in which each vertex has more than n/3 neighbours.

The Grötzsch graph has chromatic index 5, radius 2, girth 4 and diameter 2. It is also a 3-vertex-connected and 3-edge-connected graph. The independence number is 5, and the domination number is 3.

Algebraic properties

The full automorphism group of the Grötzsch graph is isomorphic to the dihedral group D5 of order 10, the group of symmetries of a regular pentagon, including both rotations and reflections.

The characteristic polynomial of the Grötzsch graph is

-(x-1)^{5}(x^{2}-x-10)(x^{2}+3x+1)^{2}.\

See also

References

  • Chvátal, Vašek (1974), "The minimality of the Mycielski graph", Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Berlin: Lecture Notes in Mathematics, Vol. 406, Springer-Verlag, pp. 243–246, MR 0360330 .
  • Erdős, P.; Simonovits, M. (1973), "On a valence problem in extremal graph theory", Discrete Mathematics 5 (4): 323–334, doi:10.1016/0012-365X(73)90126-X, MR 0342429 .
  • 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 .
  • Häggkvist, R. (1981), "Odd cycles of specified length in nonbipartite graphs", Graph Theory (Cambridge, 1981), pp. 89–99, MR 0671908 .
  • Mycielski, Jan (1955), "Sur le coloriage des graphs", Colloq. Math. 3: 161–162, MR 0069494 .

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.