k-kolorowalność grafu.
: 25 maja 2014, o 16:27
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}\).
Kod: Zaznacz cały
https://en.wikipedia.org/wiki/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theoremTakże tutaj:
Obóz OM 2016, str. 63: