{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:43:25Z","timestamp":1760298205277},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112652"},{"type":"electronic","value":"9783642112669"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11266-9_36","type":"book-chapter","created":{"date-parts":[[2009,12,7]],"date-time":"2009-12-07T09:04:58Z","timestamp":1260176698000},"page":"428-439","source":"Crossref","is-referenced-by-count":3,"title":["New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes"],"prefix":"10.1007","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"36_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/11672142_43","volume-title":"STACS 2006","author":"D. Berwanger","year":"2006","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: DAG-Width and Parity Games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 524\u2013536. Springer, Heidelberg (2006)"},{"key":"36_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0166-218X(94)90019-1","volume":"54","author":"B. Courcelle","year":"1994","unstructured":"Courcelle, B.: The Monadic Second Order-Logic of Graphs\u00a0VI: on Several Representations of Graphs by Relational Structures. Discrete Appl. Math.\u00a054, 117\u2013149 (1994)","journal-title":"Discrete Appl. Math."},{"key":"36_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11611257_20","volume-title":"SOFSEM 2006: Theory and Practice of Computer Science","author":"J.-F. Culus","year":"2006","unstructured":"Culus, J.-F., Demange, M.: Oriented Coloring: Complexity and Approximation. In: Wiedermann, J., Tel, G., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2006. LNCS, vol.\u00a03831, pp. 226\u2013236. Springer, Heidelberg (2006)"},{"issue":"4","key":"36_CR4","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1307\/mmj\/1028998975","volume":"10","author":"L. Eggan","year":"1963","unstructured":"Eggan, L.: Transition Graphs and the Star-Height of Regular Events. Michigan Mathematical Journal\u00a010(4), 385\u2013397 (1963)","journal-title":"Michigan Mathematical Journal"},{"key":"36_CR5","series-title":"Lecture Notes in Computer Science","volume-title":"IWOCA 2009, Extended Abstract","author":"R. Ganian","year":"2009","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P.: Better Polynomial Algorithms on Graphs of Bounded Rank-Width. In: IWOCA 2009, Extended Abstract. LNCS. Springer, Heidelberg (to appear, 2009)"},{"key":"36_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/978-3-642-11269-0_15","volume-title":"IWPEC 2009","author":"R. Ganian","year":"2009","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Langer, A., Obdr\u017e\u00e1lek, J., Rossmanith, P.: On Digraph Width Measures in Parameterized Algorithmics. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 185\u2013197. Springer, Heidelberg (2009)"},{"issue":"3","key":"36_CR7","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.tcs.2008.02.038","volume":"399","author":"P. Hunter","year":"2008","unstructured":"Hunter, P., Kreutzer, S.: Digraph Measures: Kelly Decompositions, Games, and Orderings. Theor. Comput. Sci.\u00a0399(3), 206\u2013219 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"36_CR8","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T. Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed Treewidth. J.\u00a0Combin. Theory Ser.\u00a0B\u00a082(1), 138\u2013154 (2001)","journal-title":"J.\u00a0Combin. Theory Ser.\u00a0B"},{"key":"36_CR9","unstructured":"Kant\u00e9, M.: The Rank-Width of Directed Graphs. arXiv:0709.1433v3 (2008)"},{"issue":"6","key":"36_CR10","doi-asserted-by":"crossref","first-page":"1024","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J. Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Tree-Depth, Subgraph Coloring and Homomorphism Bounds. European J. Combin.\u00a027(6), 1024\u20131041 (2006)","journal-title":"European J. Combin."},{"issue":"1","key":"36_CR11","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1006\/jctb.2000.1977","volume":"80","author":"J. Ne\u0161et\u0159il","year":"2000","unstructured":"Ne\u0161et\u0159il, J., Raspaud, A.: Colored Homomorphisms of Colored Mixed Graphs. J.\u00a0Combin. Theory Ser.\u00a0B\u00a080(1), 147\u2013155 (2000)","journal-title":"J.\u00a0Combin. Theory Ser.\u00a0B"},{"key":"36_CR12","doi-asserted-by":"crossref","unstructured":"Obdr\u017e\u00e1lek, J.: DAG-Width: Connectivity Measure for Directed Graphs. In: SODA 2006, pp. 814\u2013821. ACM-SIAM (2006)","DOI":"10.1145\/1109557.1109647"},{"issue":"2","key":"36_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.: Graph Minors X. Obstructions to Tree-Decomposition. J.\u00a0Combin. Theory Ser.\u00a0B\u00a052(2), 153\u2013190 (1991)","journal-title":"J.\u00a0Combin. Theory Ser.\u00a0B"},{"key":"36_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/S0012-365X(00)00216-8","volume":"229","author":"\u00c9. Sopena","year":"2001","unstructured":"Sopena, \u00c9.: Oriented Graph Coloring. Discrete Math.\u00a0229, 359\u2013369 (2001)","journal-title":"Discrete Math."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2010: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11266-9_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T04:45:03Z","timestamp":1558673103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11266-9_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642112652","9783642112669"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11266-9_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}