On the Complexity of Ordered Colorings
Arvind Gupta, Jan van den Heuvel, Ján Maňuch, Ladislav Stacho, Xiaohong Zhao · SIAM Journal on Discrete Mathematics · 2008
We introduce two variants of proper colorings with imposed partial ordering on the set of colors. One variant shows very close connections to some fundamental problems in graph theory, e.g., directed graph homomorphism and list colorings. We study the border between tractability and intractability for both variants.