Grötzsch graph

Grötzsch graph

infobox graph
name = Grötzsch graph


namesake = Herbert Grötzsch
vertices = 11
edges = 20
chromatic_number = 4
chromatic_index =
girth = 4
properties = 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 (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 M. 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 neighbors.

References

*cite conference
author = Chvátal, Vašek
authorlink = Václav Chvátal
title = The minimality of the Mycielski graph
booktitle = Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973)
date = 1974
pages = 243–246
publisher = Lecture Notes in Mathematics, Vol. 406, Springer-Verlag
location = Berlin
id = MathSciNet | id = 0360330

*cite journal
author = Erdős, P.; Simonovits, M.
title = On a valence problem in extremal graph theory
journal = Discrete Mathematics
volume = 5
year = 1973
pages = 323–334
id = MathSciNet | id = 0342429
doi = 10.1016/0012-365X(73)90126-X

*cite journal
author = Grötzsch, Herbert
title = Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel
journal = Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe
volume = 8
year = 1959
pages = 109–120
id = MathSciNet | id = 0116320

*cite conference
author = Häggkvist, R.
title = Odd cycles of specified length in nonbipartite graphs
booktitle = Graph Theory (Cambridge, 1981)
date = 1981
pages = 89–99
id = MathSciNet | id = 0671908

*cite journal
author = Mycielski, Jan
title = Sur le coloriage des graphs
journal = Colloq. Math.
volume = 3
year = 1955
pages = 161–162
id = MathSciNet | id = 0069494

External links

*mathworld | title = Grötzsch Graph | urlname = GroetzschGraph


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. 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… …   Wikipedia

  • 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,… …   Wikipedia

  • Herbert Grötzsch — Camillo Herbert Grötzsch[1] (* 21. Mai 1902 in Döbeln; † 15. Mai 1993 in Halle) war ein deutscher Mathematiker, der sich vor allem mit Funktionentheorie und Graphentheorie beschäftigte. Her …   Deutsch Wikipedia

  • Girth (graph theory) — In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.[1] If the graph does not contain any cycles (i.e. it s an acyclic graph), its girth is defined to be infinity.[2] For example, a 4 cycle (square) has… …   Wikipedia

  • Graphe de Grötzsch — Représentation du graphe de Grötzsch. Nombre de sommets 11 Nombre d arêtes 20 Distribution des degrés 3 (5 sommets) 4 (5 sommets) 5 (1 sommet) Rayon …   Wikipédia en Français

  • Chvátal graph — Named after Václav Chvátal Vertices 12 Edges 24 …   Wikipedia

  • Mycielskian — In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph G is a graph μ(G) formed from G by a construction of Jan Mycielski (1955), who used it to show that there exist triangle free graphs with… …   Wikipedia

  • Mycielski — is a surname of Polish origin, and may refer to: Dołęga Mycielski, Polish noble family Anna Luiza Mycielska, Polish noble lady Jan Mycielski, Polish American mathematician The Mycielskian, a construction in graph theory The Grötzsch graph,… …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Scheinerman's conjecture — In mathematics, Scheinerman s conjecture 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 (1984), following earlier results… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”