Image:Fourth Mycielski graph.svg
From Wikipedia, the free encyclopedia
Fourth_Mycielski_graph.svg (480 × 460 pixel, file size: 8 KB, MIME type: image/svg+xml)
| This is a file from the Wikimedia Commons. The description on its description page there is shown below. |
[edit] Summary
Very hastily drawn image of the fourth Mycielski graph. Mycielski proved in 1955 that for every 
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 k-chromatic graph G with no triangle. Take 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 k + 1-chromatic.
If you can make the image look better, by all means do so.
[edit] Licensing
 |
I, the copyright holder of this work, hereby release it into the public domain. This applies worldwide. In case this is not legally possible: Afrikaans | Alemannisch | Aragonés | العربية | Български | Català | Česky | Cymraeg | Dansk | Deutsch | Ελληνικά | English | Español | Esperanto | Euskara | فارسی | Français | Galego | 한국어 | हिन्दी | Hrvatski | Ido | Bahasa Indonesia | Íslenska | Italiano | עברית | Kurdî / كوردي | Latina | Lietuvių | Magyar | Bahasa Melayu | Nederlands | Norsk (bokmål) | Norsk (nynorsk) | 日本語 | Polski | Português | Ripoarish | Română | Русский | Shqip | Slovenčina | Slovenščina | Српски | Svenska | ไทย | Türkçe | Українська | Tiếng Việt | Walon | 简体中文 | 繁體中文 | 粵語 | +/- |
