Kolorowanie krawędziowe grafów planarnych

Speaker(s)

Łukasz Kowalik

Affiliation

Uniwersytet Warszawski

Date

Nov. 4, 2004, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---