k-kolorowalność grafu.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

k-kolorowalność grafu.

Post autor: matinf »

Udowodnij, że graf jest \(\displaystyle{ k}\)-kolorowany wtw gdy można tak acyklicznie zorientować krawędzie, że nie istnieje ścieżka zorientowana długości \(\displaystyle{ k}\).
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

k-kolorowalność grafu.

Post autor: Mruczek »

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem


Także tutaj:
Obóz OM 2016, str. 63:
ODPOWIEDZ