{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:43:56Z","timestamp":1787323436264,"version":"build-2736575974"},"reference-count":4,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/060676222","type":"journal-article","created":{"date-parts":[[2008,4,25]],"date-time":"2008-04-25T18:08:21Z","timestamp":1209146901000},"page":"832-847","source":"Crossref","is-referenced-by-count":1,"title":["On the Complexity of Ordered Colorings"],"prefix":"10.1137","volume":"22","author":[{"given":"Arvind","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"van den Heuvel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e1n","family":"Ma\u0148uch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ladislav","family":"Stacho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaohong","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,4,25]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0401029"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 3rd ed., Springer-Verlag, Berlin, 2005.","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0205048"},{"key":"R4","unstructured":"M. Garey and D. Johnson,\n                      Computers and Intractability. A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman and Co., San Franciso, 1979."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060676222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:02:20Z","timestamp":1787320940000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060676222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":4,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/060676222"],"URL":"https:\/\/doi.org\/10.1137\/060676222","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}