On the complexity of ordered colorings

; Manuch, Jan; Stacho, Ladislav; and Zhao, Xiaohong (2008) On the complexity of ordered colorings. SIAM Journal on Discrete Mathematics, 22 (2). pp. 832-847. ISSN 0895-4801

Copy

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.

Item Type	Article
Departments	Mathematics
DOI	10.1137/060676222
Date Deposited	18 Feb 2009 12:11
URI	https://researchonline.lse.ac.uk/id/eprint/22846

Explore Further

Gupta, Arvind
van den Heuvel, Jan
Manuch, Jan
Stacho, Ladislav
Zhao, Xiaohong

QA Mathematics

Full text not available from this repository.

Atom

BibTeX

OpenURL ContextObject in Span

OpenURL ContextObject

Dublin Core

MPEG-21 DIDL

Data Cite XML

EndNote

HTML Citation

METS

MODS

RIOXX2 XML

Reference Manager

Refer

ASCII Citation

Export

Downloads