Resumo

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.

Permesiloj:

Ĉi tiu verko estis liberigita kiel publika havaĵo de ties aŭtoro, Bkell. Tio aplikatas tutmonde. En iuj landoj tio povas esti laŭleĝe neebla; en tiu okazo: Bkell donas al iu ajn la rajton uzi ĉi tiun verkon por iu ajn uzo, sen kondiĉoj, krom se tiuj kondiĉoj deviĝas per leĝo.

Originala alŝutada protokolo