Graf Mycielskiego lub Mycielskian nieskierowanego grafu G – graf μ(G) stworzony dzięki konstrukcji podanej przez Jana Mycielskiego w roku 1955, pokazującej istnienie grafu, w którym największa klika ma rozmiar ≤ 2, o bezwzględnie dużej liczbie chromatycznej.
Uogólniona wersja konstrukcji została przedstawiona przez Wensonga Lin w roku 2006.
Niech n wierzchołków grafu G będzie oznaczonych v0, v1, ..., vn−1. Graf Mycielskiego μ(G) zawiera graf G jako izomorficzny podgraf oraz n+1 dodatkowych wierzchołków: ui odpowiadające wierzchołkom vi oraz wierzchołek w. Każdy wierzchołek ui jest połączony krawędzią z wierzchołkiem w tak, że tworzą one razem podgraf przypominający gwiazdę o n+1 wierzchołkach. Dodatkowo, dla każdej krawędzi vivj w ramach konstrukcji dodawane są krawędzie uivj oraz viuj.
Dla grafu G o n wierzchołkach i m krawędzich powstaje graf μ(G) o 2n+1 wierzchołkach i 3m+n krawędziach.
Ilustracja przedstawia konstrukcję grafu Mycielskiego zastosowana dla grafu cyklicznego o 5 wierzchołkach. Powstały graf jest nazywany grafem Grötzscha, ma 11 wierzchołków i 20 krawędzi. Jest to najmniejszy graf w którym największa klika ma rozmiar ≤ 2 o liczbie chromatycznej równej 4.
Stosując konstrukcję Mycielskiego, zaczynając od dwukliki K2 można otrzymać sekwencję Mi = μ(Mi−1), nazywaną czasami grafami Mycielskiego. Kilka pierwszych grafów otrzymanych w ten sposób to: graf M1 = K2 z dwoma wierzchołkami połączonymi krawędzią, graf M2 = C5 oraz M3 – graf Grötzscha z 11 wierzchołkami i 20 krawędziami.
Ogólnie, dla grafu Mi należącego do sekwencji nie istnieje klika o rozmiarze > 2, usunięcie mniej niż i wierzchołków nie powoduje utraty spójności grafu, jest on także i+1-kolorowalny. Mi ma 3 × 2i−1 − 1 wierzchołków (sekwencja A083329 w OEIS). Ilość krawędzi dla grafu Mi przy początkowych wartościach i to:
Dowód Niech c : μ(G) → C będzie minimalnym pokolorowaniem, tzn. obraz c(μ(G)) ma moc równą liczbie chromatycznej grafu Mycielskiego μ(G), czyli
(zgodnie z definicją pokolorowania grafu, wierzchołki sąsiednie różnią się kolorem).
Pokażmy, że χ(μ(G)) > χ(G): w przeciwnym wypadku wszystkie kolory c(ui) (0 ≤ i < n), a także kolor c(w), występują wśród kolorów c(vi) (0 ≤ i < n). Ale kolor c(w) nie występuje wśród c(ui). Zdefiniujmy pokolorowanie d grafu G jak następuje:
dla i = 0, ..., n−1. Pokolorowanie d, grafu G, użyło nie więcej niż χ(G) − 1 kolorów – sprzeczność. Udowodniliśmy więc, że
Niech teraz d : G → D będzie minimalnym pokolorowaniem grafu G. Zdefiniujmy:
dla i = 0, ..., n−1. Ponadto niech kolor c(w) nie należy do D. Wtedy c jest pokolorowaniem grafu Mycielskiego, które użyło tylko jednego koloru spoza D. Udowodniliśmy więc, że
co w połączeniu z poprzednią nierównością (odwrotną) kończy dowód.
Na podstawie angielskiej Wikipedii:
Uczę się języka hebrajskiego. Tutaj go sobie utrwalam.
Zawartość tej strony pochodzi stąd.