Opis

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.

Licencja

Ten utwór został udostępniony jako własność publiczna przez jego autora, Bkell. Dotyczy to całego świata. W niektórych krajach może nie być to prawnie możliwe, jeśli tak, to: Bkell zapewnia każdemu prawo do użycia tej pracy w dowolnym celu, bez żadnych ograniczeń, chyba że te ograniczenia są wymagane przez prawo.

Oryginalny rejestr przesyłania