{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:32:47Z","timestamp":1760297567046},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540311980"},{"type":"electronic","value":"9783540322177"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11611257_20","type":"book-chapter","created":{"date-parts":[[2006,1,5]],"date-time":"2006-01-05T16:37:18Z","timestamp":1136479038000},"page":"226-236","source":"Crossref","is-referenced-by-count":9,"title":["Oriented Coloring: Complexity and Approximation"],"prefix":"10.1007","author":[{"given":"Jean-Fran\u00e7ois","family":"Culus","sequence":"first","affiliation":[]},{"given":"Marc","family":"Demange","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","unstructured":"Demange, M., Ekim, T., de Werra, D.: On the Approximation of Min Split-Coloring and Min Cocoloring (manuscript)"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0304-3975(97)00099-6","volume":"209","author":"M. Demange","year":"1998","unstructured":"Demange, M., Grisoni, P., Paschos, V.T.: Differential Approximation Algorithms for Some Combinatorial Optimization Problems. Theoretical Computer Science\u00a0209, 107\u2013122 (1998)","journal-title":"Theoretical Computer Science"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Duh, R., F\u00fcrer, M.: Approximation of k-Set Cover by Semi-Local Optimization. In: Proc. of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 256\u2013264 (1997)","DOI":"10.1145\/258533.258599"},{"key":"20_CR4","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: A Still Better Performance Quarantee for Approximate Graph Coloring. Information Processing Letters\u00a045, 19\u201323 (1993)","journal-title":"Information Processing Letters"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1006\/jagm.2001.1187","volume":"41","author":"R. Hassin","year":"2001","unstructured":"Hassin, R., Khuller, S.: z-Approximations. Journal of Algorithms\u00a041, 429\u2013442 (2001)","journal-title":"Journal of Algorithms"},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0020-0190(94)00113-8","volume":"52","author":"R. Hassin","year":"1994","unstructured":"Hassin, R., Lahav, S.: Maximizing the Number of Unused Colors in the Vertex Coloring Problem. Information Processing Letters\u00a052, 87\u201390 (1994)","journal-title":"Information Processing Letters"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"18","author":"P. Hell","year":"1990","unstructured":"Hell, P., Nesetril, J.: On the Complexity of h-Coloring. Journal of Combinatorial Theory (B)\u00a018, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory (B)"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Hell, P., Nesetril, J.: Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications (2004)","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences\u00a09, 256\u2013278 (1974)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Kierstead, H.A., Trotter, W.T.: Competitive Colorings of Oriented Graphs. Electronic Journal of Combinatorics\u00a08 (2001)","DOI":"10.37236\/1611"},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0012-365X(03)00086-4","volume":"274","author":"W.F. Klostermeyer","year":"2004","unstructured":"Klostermeyer, W.F., MacGillivray, G.: Homomorphisms and Oriented Colorings of Equivalence Classes of Oriented Graphs. Discrete Mathematics\u00a0274, 161\u2013172 (2004)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"20_CR13","doi-asserted-by":"crossref","first-page":"14","DOI":"10.37236\/1613","volume":"8","author":"J. Nesetril","year":"2001","unstructured":"Nesetril, J., Sopena, E.: On the Oriented Game Chromatic Number. The Electronic Journal of Combinatorics\u00a08(2), R14 (2001)","journal-title":"The Electronic Journal of Combinatorics"},{"issue":"1","key":"20_CR14","first-page":"125","volume":"38","author":"J. Nesetril","year":"1997","unstructured":"Nesetril, J., Sopena, E., Vignal, L.: t-Preserving Homomorphisms of Oriented Graphs. Comment. Math. Univ. Carolinae\u00a038(1), 125\u2013136 (1997)","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"20_CR15","unstructured":"Sopena, E.: Computing Chromatic Polynomials of Oriented Graphs. In: Proc. Formal power series and Algebraic Combinatorics. DIMACS, pp. 413\u2013422 (1994)"},{"issue":"1-3","key":"20_CR16","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/S0012-365X(00)00216-8","volume":"229","author":"Eric Sopena","year":"2001","unstructured":"Sopena, E.: Oriented Graph Coloring. Discrete Mathematics\u00a0229 (2001)","journal-title":"Discrete Mathematics"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Wood, D.R.: Acyclic, Star and Oriented Colorings of Graph Subdivisions (2005) (submitted)","DOI":"10.46298\/dmtcs.344"},{"key":"20_CR18","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1287\/moor.6.3.319","volume":"6","author":"E. Zemel","year":"1981","unstructured":"Zemel, E.: Measuring the Quality of Approximate Solutions to Zero-One Programming Problems. Mathematics of Operations Research\u00a06, 319\u2013332 (1981)","journal-title":"Mathematics of Operations Research"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2006: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11611257_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T02:56:23Z","timestamp":1683341783000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11611257_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540311980","9783540322177"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11611257_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}