On the complexity of ordered colorings
Gupta, A., van den Heuvel, J.
, Manuch, J., Stacho, L. & Zhao, X.
(2008).
On the complexity of ordered colorings.
SIAM Journal on Discrete Mathematics,
22(2), 832-847.
https://doi.org/10.1137/060676222
, Manuch, J., Stacho, L. & Zhao, X.
(2008).
On the complexity of ordered colorings.
SIAM Journal on Discrete Mathematics,
22(2), 832-847.
https://doi.org/10.1137/060676222
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.