Uporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków, aby każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawierała wierzchołek o kolorze wyższym. Jeśli każdy wierzchołek posiada dodatkowo listę dozwolonych dla niego etykiet, to mówimy wówczas o uporządkowanym listowym kolorowaniu wierzchołków. W pracy wskazano szereg klas grafów, dla których problem jest trudny: pełne drzewa binarne, drzewa o średnicy co najwyżej 4, komety oraz grafy krawędziowe tych klas. Z drugiej strony ścieżki, drzewa o ograniczonej liczbie wierzchołków wewnętrznych to przypadki, dla których opisano algorytmy wielomianowe.
Authors
Additional information
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie z listy filadelfijskiej
- Language
- angielski
- Publication year
- 2008
Source: MOSTWiedzy.pl - publication "The complexity of list ranking of trees" link open in new tab
