{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:11Z","timestamp":1740107111701,"version":"3.37.3"},"reference-count":8,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,8,21]],"date-time":"2022-08-21T00:00:00Z","timestamp":1661040000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,21]],"date-time":"2022-08-21T00:00:00Z","timestamp":1661040000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Oriented coloring of an oriented graph <jats:italic>G<\/jats:italic> is an arc-preserving homomorphism from <jats:italic>G<\/jats:italic> into a tournament <jats:italic>H<\/jats:italic>. We say that the graph <jats:italic>H<\/jats:italic> is universal for a family of oriented graphs <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {C}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>C<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if for every <jats:inline-formula><jats:alternatives><jats:tex-math>$$G\\in \\mathcal {C}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>C<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> there exists a homomorphism from <jats:italic>G<\/jats:italic> into <jats:italic>H<\/jats:italic>. We are interested in finding a universal graph for the family of orientations of cubic graphs. In this paper we present constructive proof that: if there exists a universal graph <jats:italic>H<\/jats:italic> on 7 vertices for every orientation of cubic graphs, then minimum out-degree and minimum in-degree of <jats:italic>H<\/jats:italic> are equal to 2. That gives a negative answer to the question presented in Pinlou\u2019s PHD thesis.<\/jats:p>","DOI":"10.1007\/s00373-022-02549-0","type":"journal-article","created":{"date-parts":[[2022,8,21]],"date-time":"2022-08-21T18:02:22Z","timestamp":1661104942000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Coloring Graphs in Oriented Coloring of Cubic Graphs"],"prefix":"10.1007","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2575-4373","authenticated-orcid":false,"given":"Janusz","family":"Dybizba\u0144ski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,21]]},"reference":[{"issue":"10","key":"2549_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2020.112021","volume":"343","author":"C Duffy","year":"2020","unstructured":"Duffy, C.: Colourings of oriented connected cubic graphs. Discret. Math. 343(10), 112021 (2020)","journal-title":"Discret. Math."},{"issue":"4","key":"2549_CR2","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1016\/j.disc.2018.10.008","volume":"342","author":"C Duffy","year":"2019","unstructured":"Duffy, C., MacGillivray, G., Sopena, \u00c9.: Oriented colourings of graphs with maximum degree three and four. Discret. Math. 342(4), 959\u2013974 (2019)","journal-title":"Discret. Math."},{"issue":"5","key":"2549_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2020.111829","volume":"343","author":"J Dybizba\u0144ski","year":"2020","unstructured":"Dybizba\u0144ski, J., Ochem, P., Pinlou, A., Szepietowski, A.: Oriented cliques and colorings of graphs with low maximum degree. Discret. Math. 343(5), 111829 (2020)","journal-title":"Discret. Math."},{"key":"2549_CR4","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO;2-P","volume":"24","author":"AV Kostochka","year":"1997","unstructured":"Kostochka, A.V., Sopena, \u00c9., Zhu, X.: Acyclic and oriented chromatic numbers of graphs. J. Graph Theory 24, 331\u2013340 (1997)","journal-title":"J. Graph Theory"},{"key":"2549_CR5","unstructured":"Pinlou, A.: Arc-coloration et sommet-coloration orient\u00e9es, PhD Thesis (in French), Universit\u00e9 Bordeaux-I (2006)"},{"key":"2549_CR6","doi-asserted-by":"publisher","first-page":"1993","DOI":"10.1016\/j.disc.2015.03.018","volume":"339","author":"\u00c9 Sopena","year":"2016","unstructured":"Sopena, \u00c9.: Homomorphisms and colourings of oriented graphs: An updated survey. Discret. Math. 339, 1993\u20132005 (2016)","journal-title":"Discret. Math."},{"key":"2549_CR7","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1002\/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G","volume":"25","author":"\u00c9 Sopena","year":"1997","unstructured":"Sopena, \u00c9.: The chromatic number of oriented graphs. J. Graph Theory 25, 191\u2013205 (1997)","journal-title":"J. Graph Theory"},{"key":"2549_CR8","unstructured":"Sopena, \u00c9., Vignal, L.: A note on the Oriented Chromatic number of Graphs with Maximum Degree, Three. Technical report, LaBRI, University of Bordeaux I (1996)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02549-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-022-02549-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02549-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,2]],"date-time":"2022-11-02T19:44:45Z","timestamp":1667418285000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-022-02549-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,21]]},"references-count":8,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["2549"],"URL":"https:\/\/doi.org\/10.1007\/s00373-022-02549-0","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2022,8,21]]},"assertion":[{"value":"5 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"147"}}