File:Grötzsch graph.svg

Summary[edit]

Very hastily drawn image of the fourth Mycielski graph. Mycielski proved in 1955 that for every ${\displaystyle k\geq 1}$ there is a graph with chromatic number k that contains no triangle subgraphs, that is, whose maximal clique size is just 2. (This was also proved by A. A. Zykov, Mat. Zb. 24, (1949), 2, 163-183 (in Russian) and by "Blanche Descartes" (W. T. Tutte) Amer. Math. Monthly 61, (1954) p. 352.) The chromatic number of this graph is 4.

A simple construction of triangle-free graphs of any chromatic number is this. Start with a ${\displaystyle k}$-chromatic graph G with no triangle. Take ${\displaystyle k}$ copies of G. Form all sets consisting of 1 node from each copy. Connect the nodes in each of these sets to a new node. The resulting graph is triangle-free and ${\displaystyle k+1}$-chromatic.

If you can make the image look better, by all means do so.

Licensing[edit]

This work has been released into the public domain by its author, Bkell. This applies worldwide. In some countries this may not be legally possible; if so: Bkell grants anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

Original upload log[edit]