Uporządkowane kolorowane wierzchołki grafów

W pracy przedstawiamy stosunkowo nowy model kolorowania grafów, mianowicie kolorowanie uporządkowane. Po scharakteryzowaniu potencjalnych zastosowań tego modelu przedstawiamy liniowy algorytm kolorowania grafów w sposób przybliżony. Pokazujemy klasy grafów, które ten algorytm koloruje optymalnie i klasy grafów, dla których błąd pokolorowania może być dowolnie duży. Przedstawiamy również doświadczenia komputerowe zebrane w trakcie jego implementacji i testowania na grafach losowych.

---

We present a relatively new model of graph coloring, namely ordered (rank) coloring. After characterizing potential applications of this model, we give a linear-time algorithm KU for approximate graph coloring. We show graph classes that our algorithm colors optimally and graph classes that can be colored arbitrarily bad. Finally, we give results of computational experiments gained while testing algorithm KU on random graphs.