Image:Fourth Mycielski graph.svg

From Wikipedia, the free encyclopedia

Fourth_Mycielski_graph.svg‎ (SVG file, nominally 480 × 460 pixels, file size: 8 KB)

Wikimedia Commons logo This is a file from the Wikimedia Commons. The description on its description page there is shown below.
Commons is a freely licensed media file repository. You can help.
This media object could not be renamed automatically because:
  • the rename request was made by a non-trusted user.

The requested target is Image:Grötzsch graph.svg. A user trusted for this purpose should correct this by:

English | +/-

[edit] Summary

Very hastily drawn image of the fourth Mycielski graph. Mycielski proved in 1955 that for every k\ge1 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

Public domain I, the copyright holder of this work, hereby release it into the public domain. This applies worldwide.

In case this is not legally possible:
I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

Afrikaans | Alemannisch | Aragonés | العربية | Asturianu | Български | Català | Česky | Cymraeg | Dansk | Deutsch | Eʋegbe | Ελληνικά | English | Español | Esperanto | Euskara | Estremeñu | فارسی | Français | Galego | 한국어 | हिन्दी | Hrvatski | Ido | Bahasa Indonesia | Íslenska | Italiano | עברית | Kurdî / كوردی | Latina | Lietuvių | Latviešu | Magyar | Македонски | Bahasa Melayu | Nederlands | ‪Norsk (bokmål)‬ | ‪Norsk (nynorsk)‬ | 日本語 | Polski | Português | Ripoarisch | Română | Русский | Shqip | Slovenčina | Slovenščina | Српски / Srpski | Svenska | ไทย | Tagalog | Türkçe | Українська | Tiếng Việt | Walon | ‪中文(简体)‬ | ‪中文(繁體)‬ | zh-yue-hant | +/-

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeDimensionsUserComment
current09:37, 17 December 2006480×460 (8 KB)Booyabazooka (Prettier version requested... how's this?)
10:33, 3 July 2006700×700 (6 KB)Bkell (Very hastily drawn image of the fourth Mycielski graph. Mycielski proved in 1955 that for every <math>k\ge1</math> there is a graph with chromatic number ''k'' that contains no triangle subgraphs, that is, whose maximal clique size is just 2. The chromati)
The following pages on the English Wikipedia link to this file (pages on other projects are not listed):