Kolorowanie krawędziowe grafów planarnych

Prelegent(ci)

Łukasz Kowalik

Afiliacja

Uniwersytet Warszawski

Termin

4 listopada 2004 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

W problemie kolorowania krawędziowego grafu należy krawędziom grafu przypisać kolory tak, aby incydentne krawędzie otrzymały różne kolory. Rozważa się bardzo naturalne uogólnienie tego problemu: listowe kolorowanie krawędziowe. W tej wersji każda krawędź ma przypisaną listę dozwolonych kolorów. Na seminarium opowiem o algorytmach kolorowania krawędziowego i listowego kolorowania krawędziowego grafów planarnych. Będą nas interesowały wyłącznie liniowe algorytmy i optymalne kolorowanie -- używające możliwie małej liczby kolorów lub działające dla możliwie krótkich list. Opowiem o nowych wynikach w tej dziedzinie, uzyskanych we współpracy z Richardem Cole.

---