spezielle Graphen, die zeigen, daß es zu jeder natürlichen Zahl k ≥ 2 einen k-chromatischen Graphen ohne Kreise der Länge 3 gibt.

Ist ω(G) die Cliquenzahl und χ(G) die chromatische Zahl eines Graphen G, so gilt natürlich die Ungleichung χ(G) ≥ ω(G). Eine Konstruktion von J. Mycielski aus dem Jahre 1955 liefert dagegen ein Familie von Graphen mit willkürlich hohen chromatischen Zahlen, deren Cliquenzahl dennoch nur 2 beträgt.

Für die vorgegebenen Zahlen k = 2 bzw. k = 3 haben der vollständige Graph K₂ bzw. der Kreis der Länge 5 die gewünschten Eigenschaften. Bezeichnen wir diese beiden Graphen mit M₂ bzw. M₃, so werden für k ≥ 3 die Mycielski-Graphen M_k+1 rekursiv wie folgt definiert.

Ist {v₁, v₂,…,v_n} die Eckenmenge von M_k, so konstruiert man den Graphen M_k+1 aus M_k durch Hinzufügen von n + 1 neuen Ecken u, u₁, u₂,… ,u_n. Darüber hinaus wird für i = 1, 2,… ,n die Kante uu_i hinzugefügt, und eine Ecke u_i wird mit einer Ecke v ∈ E(M_k) durch eine Kante verbunden, wenn v in M_k zu v_i adjazent ist.

Aus der Tatsache, daß M_k keinen Kreis der Länge 3 enthält, folgt unmittelbar, daß auch M_k+1 keinen solchen Kreis besitzen kann. Mit etwas mehr Aufwand läßt sich dann noch χ(M_k+1) = k + 1 nachweisen. M₄ ist gerade der bekannte Grötzsch-Graph.