Kolorowanie krawędziowe grafów planarnych

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.