201306051651

•    Jeśli G jest grafem bez pętli, to mówimy, że G jest grafem k- kolor owalnym, jeśli każdemu wierzchołkowi możemy przypisać jeden z k kolorów w taki sposób, by sąsiednie wierzchołki miały różne kolory.

X(G) = k.

•    Jeśli graf G jest fc-kolorowalny, ale nie jest (fc — l)-kolorowalny, to mówimy, że jego liczba chromatyczna jest równa fc; piszemy wtedy

Twierdzenie Jeśli G jest grafem prostym, w którym największym stopniem wierz-

chołka jest A, to graf G jest (A + l)-kolorowalny.

to graf G A-kolorowalny.

Twierdzenie Brooks, 1941 Jeśli G jest spójnym grafem prostym, nie będącym grafem pełnym , i jeśli największy stopień wierzchołka grafu G wynosi A (gdzie A > 3), ■    0    to graf G A-kolorowalny.

• Grafem planarnym nazywamy graf, który można narysować na płaszczyźnie bez przecięć, to znaczy tak, by żadne dwie krawędzie nie przecinały się na rysunku poza wierzchołkiem, z którym obie są incydentne.

Twierdzenie Każdy planarny graf prosty jest 6-kolorowalny. Twierdzenie Każdy planarny graf prosty jest 5-kolorowalny.

Tw. Appel, Haken, 1976 Każdy planarny graf prosty jest 4-kolorowalny.

•    Mówimy, że graf G jest fc-kolorowalny krawędziowo jeśli jego krawędzie można pokolorować k kolorami w taki sposób, by żadne dwie sąsiednie krawędzie nie miały tego samego koloru.

•    Jeśli graf G jest fc-kolorowalny krawędziowo, ale nie jest (fc—l)-kolorowalny krawędziowo, to mówimy, że jego indeks chromatyczny wynosi k i piszemy y!{G) = k.

Twierdzenie Vizing, 1964 Jeśli G jest grafem prostym, w którym największy stopień wierzchołka wynosi A, to A < x!{G) < A + 1.

Twierdzenie tf(K_n) = n dla n nieparzystych (n 4 1) i x!(.K_n) — n - 1 dla n parzystych.

Twierdzenie Konig, 1916 Jeśli w grafie dwudzielnym największy stopień wierzchołka wynosi A, to )d{G) = A-

1