Összefoglaló

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.

Licenc

Bkell, a mű szerzője művét közkinccsé nyilvánította. Ez a világ minden részén érvényes. Egyes országokban ez jogilag nem lehetséges. Ha így van, akkor: Bkell jogot ad bárkinek, hogy bármilyen célból, feltétel nélkül használhassa ezt a fájlt, kivéve a törvény által kötelezően előírt feltételeket.

Eredeti feltöltési napló