{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T20:16:56Z","timestamp":1760300216849,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T00:00:00Z","timestamp":1556150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GU 970\/7-1"],"award-info":[{"award-number":["GU 970\/7-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. An oriented k-coloring of an oriented graph     G = ( V , A )     is a partition of the vertex set V into k independent sets such that all the arcs linking two of these subsets have the same direction. The oriented chromatic number of an oriented graph G is the smallest k such that G allows an oriented k-coloring. Deciding whether an acyclic digraph allows an oriented 4-coloring is NP-hard. It follows that finding the chromatic number of an oriented graph is an NP-hard problem, too. This motivates to consider the problem on oriented co-graphs. After giving several characterizations for this graph class, we show a linear time algorithm which computes an optimal oriented coloring for an oriented co-graph. We further prove how the oriented chromatic number can be computed for the disjoint union and order composition from the oriented chromatic number of the involved oriented co-graphs. It turns out that within oriented co-graphs the oriented chromatic number is equal to the length of a longest oriented path plus one. We also show that the graph isomorphism problem on oriented co-graphs can be solved in linear time.<\/jats:p>","DOI":"10.3390\/a12040087","type":"journal-article","created":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T10:44:06Z","timestamp":1556189046000},"page":"87","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Oriented Coloring on Recursively Defined Digraphs"],"prefix":"10.3390","volume":"12","author":[{"given":"Frank","family":"Gurski","sequence":"first","affiliation":[{"name":"Algorithmics for Hard Problems Group, Institute of Computer Science, Heinrich Heine University D\u00fcsseldorf, 40225 D\u00fcsseldorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominique","family":"Komander","sequence":"additional","affiliation":[{"name":"Algorithmics for Hard Problems Group, Institute of Computer Science, Heinrich Heine University D\u00fcsseldorf, 40225 D\u00fcsseldorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8788-1028","authenticated-orcid":false,"given":"Carolin","family":"Rehs","sequence":"additional","affiliation":[{"name":"Algorithmics for Hard Problems Group, Institute of Computer Science, Heinrich Heine University D\u00fcsseldorf, 40225 D\u00fcsseldorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,4,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Golumbic, M. (1980). Algorithmic Graph Theory and Perfect Graphs, Academic Press.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0166-218X(94)90004-3","article-title":"Efficient algorithms for minimum weighted coloring of some classes of perfect graphs","volume":"55","year":"1994","journal-title":"Discret. Appl. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","article-title":"Complement Reducible Graphs","volume":"3","author":"Corneil","year":"1981","journal-title":"Discret. Appl. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0166-218X(94)90019-1","article-title":"The monadic second-order logic of graphs VI: On several representations of graphs by relational structures","volume":"54","author":"Courcelle","year":"1994","journal-title":"Discret. Appl. Math."},{"key":"ref_5","first-page":"226","article-title":"Oriented Coloring: Complexity and Approximation","volume":"Volume 3831","author":"Culus","year":"2006","journal-title":"Proceedings of the Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1002\/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G","article-title":"The chromatic number of oriented graphs","volume":"25","author":"Sopena","year":"1997","journal-title":"J. Graph Theory"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1489","DOI":"10.1007\/s00373-012-1202-y","article-title":"Homomorphism bounds for oriented planar graphs of given minimum girth","volume":"29","author":"Marshall","year":"2013","journal-title":"Graphs Comb."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.ipl.2013.09.011","article-title":"The oriented chromatic number of Halin graphs","volume":"114","author":"Szepietowski","year":"2014","journal-title":"Inf. Process. Lett."},{"key":"ref_9","unstructured":"Ganian, R. (2009, January 13\u201315). The Parameterized Complexity of Oriented Coloring. Proceedings of the Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS), Znojmo, Czech Republic."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1007\/3-540-62950-5_74","article-title":"A complete axiomatisation of the inclusion of series-parallel partial orders","volume":"Volume 1232","author":"Bechet","year":"1997","journal-title":"Rewriting Techniques and Applications"},{"key":"ref_11","first-page":"3","article-title":"Graphical algorithms and their complexity","volume":"81","author":"Lawler","year":"1976","journal-title":"Math. Cent. Tracts"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2015.11.003","article-title":"Directed NLC-width","volume":"616","author":"Gurski","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., and Gutin, G. (2009). Digraphs. Theory, Algorithms and Applications, Springer.","DOI":"10.1007\/978-1-84800-998-1"},{"key":"ref_14","unstructured":"Gurski, F. (2008). A comparison of two approaches for polynomial time algorithms computing basic graph parameters. arXiv."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Fomin, F., Golovach, P., Lokshtanov, D., and Saurabh, S. (2009, January 4\u20136). Clique-width: On the price of generality. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), New York, NY, USA.","DOI":"10.1137\/1.9781611973068.90"},{"key":"ref_16","first-page":"117","article-title":"How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time","volume":"Volume 2204","author":"Espelage","year":"2001","journal-title":"Proceedings of the Graph-Theoretical Concepts in Computer Science (WG)"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1016\/j.dam.2006.03.005","article-title":"Fully dynamic recognition algorithm and certificate for directed cographs","volume":"154","author":"Crespelle","year":"2006","journal-title":"Discret. Appl. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/jgt.21775","article-title":"Arc-disjoint paths in decomposable digraphs","volume":"77","author":"Maddaloni","year":"2014","journal-title":"J. Graph Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"35","DOI":"10.19139\/soic.v5i1.260","article-title":"Dynamic Programming Algorithms on Directed Cographs","volume":"5","author":"Gurski","year":"2017","journal-title":"Stat. Optim. Inf. Comput."},{"key":"ref_20","unstructured":"Retor\u00e9, C. (1997, January 15\u201317). Pomset logic as a calculus of directed cographs. Proceedings of the Fourth Roma Workshop: Dynamic perspectives in Logic and Linguistics, Roma, Italy."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/978-3-319-94776-1_22","article-title":"Directed path-width and directed tree-width of directed co-graphs","volume":"Volume 10976","author":"Gurski","year":"2018","journal-title":"Proceedings of the International Conference on Computing and Combinatorics (COCOON)"},{"key":"ref_22","first-page":"43","article-title":"Oriented Threshold Graphs","volume":"71","author":"Boeckner","year":"2018","journal-title":"Australas. J. Comb."},{"key":"ref_23","unstructured":"Gould, R. (2012). Graph Theory, Dover Publications Inc."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Hell, P., and Nesetril, J. (2004). Graphs and Homomorphisms, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"ref_25","unstructured":"Aho, A., Hopcroft, J., and Ullman, J. (1974). The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/jctb.2000.2031","article-title":"Directed Tree-width","volume":"82","author":"Johnson","year":"2001","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_27","first-page":"572","article-title":"Hardness Results for Tournament Isomorphism and Automorphism","volume":"Volume 4708","author":"Wagner","year":"2007","journal-title":"Proceedings of the Mathematical Foundations of Computer Science (MFCS)"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","article-title":"Upper bounds to the clique width of graphs","volume":"101","author":"Courcelle","year":"2000","journal-title":"Discret. Appl. Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/4\/87\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:47:11Z","timestamp":1760186831000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/4\/87"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,25]]},"references-count":28,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,4]]}},"alternative-id":["a12040087"],"URL":"https:\/\/doi.org\/10.3390\/a12040087","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,4,25]]}}}