Zadanie 1
Wierzchołki grafu permutacji $G_n$ są etykietowane permutacjami zbioru $n$-elementowego. Dwa wierzchołki w tym grafie są połączone krawędzią, jeśli odpowiadające im permutacje różnią się transpozycją sąsiednich elementów. Dla jakich $n$ graf $G_n$ jest planarny?
Zadanie 2
Pokaż nieplanarność grafu Petersena
(a) z tw. Kuratowskiego (zawiera podgraf homeomorf. z K3,3 lub K5);
(b) wyprowadzając ograniczenie górne na liczbę krawędzi dla grafów planarnych o obwodzie r.
Zadanie 3
Dla jakich k hiperkostka Qk jest planarna? Dla jakich r,s,t pełny graf trojdzielny Kr,s,t jest planarny?
Zadanie 4
Pokaż, że jeśli G ma co najmniej 11 wierzchołków, to G i dopełnienie G nie mogą być jednocześnie planarne. Podaj przykład 8-wierzchołkowego G takiego, że G i dopełnienie G są planarne.
Zadanie 5
Ile co najwyżej krawędzi może mieć n-wierzchołkowy graf zewnętrznie planarny? Pokaż, że każdy graf zewnętrznie planarny można pokolorować 3 kolorami.
Zadanie 6
Udowodnij "twierdzenie o 7 barwach" dla torusa:
a) K7 można narysować na torusie => czasem trzeba użyć 7 kolorów.
b) odpowiednik wzoru Eulera: n-m+f=0
c) odpowiednik m<=3n-6: m<=3n
d) odpowiednik faktu o istnieniu wierzchołka stopnia <=5: istnieje wierzchołek stopnia <=6
e) 7 kolorow zawsze wystarczy.
Zadanie 7
Graf Knesera K(r,n): V = {r-podzbiory {1..n}}
{A,B} jest krawędzia <=> część wspólna A i B jest pusta (Np. K(2,5) -
graf Petersena). Pokaż, ze χ(K(2,5))=3, χ(K(2,6))=4, ogólnie
χ(K(r,n))<=n-2r+2.
Zadanie 8
Graf Mycielskiego Mn: M2 = krawędź, Mk+1: do Mk dokładamy kopię M' samych wierzchołków z Mk. Każdy wierzchołek-kopia w M' jest połączony z sąsiadami swojego oryginału w Mk. Dokładamy jeszcze nowy wierzchołek połączony ze wszystkimi w M'. Pokaż, że
a) w Mk nie ma trójkątów
b) χ(M_k)=k.
Zadanie 9
Udowodnij tw. Koniga: kolorowanie krawędziowe grafu dwudzielnego o maksymalnym stopniu D wymaga tylko D kolorow.
Zadanie 10
Znajdź wielomian chromatyczny cyklu Cn, "koła o n szprychach", grafu K3,3.