From Surf Wiki (app.surf) — the open knowledge base
Grötzsch graph
Triangle-free graph requiring four colors
Triangle-free graph requiring four colors
| Field | Value | |
|---|---|---|
| name | Grötzsch graph | |
| image | [[Image:Groetzsch-graph.svg | 180px]] |
| namesake | Herbert Grötzsch | |
| vertices | 11 | |
| edges | 20 | |
| diameter | 2 | |
| radius | 2 | |
| girth | 4 | |
| chromatic_number | 4 | |
| chromatic_index | 5 | |
| crossing_number | 5 | |
| automorphisms | 10 (D5) | |
| properties | {{plainlist | 1= |
| queue number | 2 | book thickness=3 |
- Hamiltonian
- Projective planar
- 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, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 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 one-edge graph; this sequence of graphs was constructed by 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.
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. These symmetries have three orbits of vertices: the degree-5 vertex (by itself), its five neighbors, and its five non-neighbors. Similarly, there are three orbits of edges, distinguished by their distance from the degree-5 vertex.
The characteristic polynomial of the Grötzsch graph is (x-1)^5 (x^2-x-10) (x^2+3 x+1)^2.
Although it is not a planar graph, it can be embedded in the projective plane without crossings. This embedding has ten faces, all of which are quadrilaterals. The graph is 1-planar.
Applications
The existence of the Grötzsch graph demonstrates that the assumption of planarity is necessary in Grötzsch's theorem that every triangle-free planar graph is 3-colorable. It has odd girth five but girth four, and does not have any graph homomorphism to a graph whose girth is five or more, so it forms an example that distinguishes odd girth from the maximum girth that can be obtained from a homomorphism.
used a modified version of the Grötzsch graph to disprove a conjecture of 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. Every such graph contains the Grötzsch graph as an induced subgraph.
Notes
References
- {{citation
- {{citation | author-link = Václav Chvátal
- {{citation | author1-link = Paul Erdős | last1 = Erdős | first1 = P. | last2 = Simonovits | first2 = M.
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation | author-link = Jan Mycielski
- {{citation
- {{citation
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about Grötzsch graph — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report