W pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania. W niniejszym artykule dowodzimy NP-zupełność w przypadku klasy grafów cięciwowych i stałej liczby kolorów równej 3. Oszacowanie to jest najlepszym możliwym. Z drugiej strony pokazujemy, że problem optymalizacyjny można rozwiązać w liniowym czasie dla właściwych grafów przedziałowych.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.7151/dmgt.1445
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Language
- angielski
- Publication year
- 2009
