{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T21:11:04Z","timestamp":1766178664523,"version":"3.37.3"},"reference-count":23,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T00:00:00Z","timestamp":1708300800000},"content-version":"vor","delay-in-days":49,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,12,23]]},"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:p>Let<jats:italic>G<\/jats:italic>\u20d7 = (<jats:italic>V, A<\/jats:italic>) be an oriented graph and<jats:italic>G<\/jats:italic>the underlying graph of<jats:italic>G<\/jats:italic>\u20d7. An<jats:italic>oriented<\/jats:italic><jats:italic>k<\/jats:italic><jats:italic>-coloring<\/jats:italic>of<jats:italic>G<\/jats:italic>\u20d7 is a partition of<jats:italic>V<\/jats:italic>into<jats:italic>k<\/jats:italic>color classes, such that there is no pair of adjacent vertices belonging to the same class and all the arcs between a pair of color classes have the same orientation. The smallest<jats:italic>k<\/jats:italic>such that<jats:italic>G<\/jats:italic>\u20d7 admits an oriented<jats:italic>k<\/jats:italic>-coloring is the<jats:italic>oriented chromatic number<\/jats:italic><jats:italic>\u03c7<\/jats:italic><jats:italic><jats:sub>o<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>\u20d7) =<jats:italic>k<\/jats:italic>of<jats:italic>G<\/jats:italic>\u20d7. The<jats:italic>oriented chromatic number<\/jats:italic><jats:italic>\u03c7<\/jats:italic><jats:italic><jats:sub>o<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>) of the undirected graph<jats:italic>G<\/jats:italic>is the maximum of<jats:italic>\u03c7<\/jats:italic><jats:italic><jats:sub>o<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>\u20d7) for all orientations<jats:italic>G<\/jats:italic>\u20d7 of<jats:italic>G<\/jats:italic>. Oriented chromatic number of the product of two graphs<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>,<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>was widely studied, but the disjoint union<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>\u222a<\/jats:italic><jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>has not yet been considered. In this article we proved bounds for the oriented chromatic number of any two oriented graphs and we also proved that given two complete graphs<jats:italic>K<\/jats:italic><jats:italic><jats:sub>n<\/jats:sub><\/jats:italic>and<jats:italic>K<\/jats:italic><jats:italic><jats:sub>m<\/jats:sub><\/jats:italic>with<jats:italic>n<\/jats:italic><jats:italic>\u2265<\/jats:italic><jats:italic>m<\/jats:italic>, there is a real number<jats:italic>\u03b1<\/jats:italic><jats:italic>\u2208<\/jats:italic>(1, 3) such that<jats:italic>\u03c7<\/jats:italic><jats:italic><jats:sub>o<\/jats:sub><\/jats:italic>(<jats:italic>K<\/jats:italic><jats:italic><jats:sub>n<\/jats:sub><\/jats:italic><jats:italic>\u222a<\/jats:italic><jats:italic>K<\/jats:italic><jats:italic><jats:sub>m<\/jats:sub><\/jats:italic>) =<jats:italic>n<\/jats:italic>+<jats:italic>m<\/jats:italic><jats:italic>\u2212<\/jats:italic><jats:italic>\u03b1<\/jats:italic>log<jats:sub>2<\/jats:sub>(<jats:italic>m<\/jats:italic>). Additionally, we established exact values of the union of one complete graph with one cycle and of one complete graph with a forest.<\/jats:p>","DOI":"10.1051\/ro\/2024005","type":"journal-article","created":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T19:53:16Z","timestamp":1704397996000},"page":"579-590","source":"Crossref","is-referenced-by-count":1,"title":["On the oriented coloring of the disjoint union of graphs"],"prefix":"10.1051","volume":"58","author":[{"given":"Erika Morais Martins","family":"Coelho","sequence":"first","affiliation":[]},{"given":"Hebert","family":"Coelho da Silva","sequence":"additional","affiliation":[]},{"given":"Luerbio","family":"Faria","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5585-5423","authenticated-orcid":false,"given":"Mateus","family":"de Paula Ferreira","sequence":"additional","affiliation":[]},{"given":"Sylvain","family":"Gravier","sequence":"additional","affiliation":[]},{"given":"Sulamita","family":"Klein","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2024,2,19]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/eujc.1997.0148","volume":"19","author":"Alon","year":"1998","journal-title":"Eur. J. Comb."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Babai L. and Luks E.M., Canonical labeling of graphs, in Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25\u201327 April, 1983. ACM, Boston, Massachusetts, USA (1983) 171\u2013183.","DOI":"10.1145\/800061.808746"},{"key":"R3","unstructured":"Bondy A. and Murty U.S.R., Graph Theory. Graduate Texts in Mathematics. Springer London (2011)."},{"key":"R4","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0012-365X(98)00393-8","volume":"206","author":"Borodin","year":"1999","journal-title":"Discrete Math."},{"key":"R5","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.dam.2015.06.023","volume":"198","author":"Coelho","year":"2016","journal-title":"Discret. Appl. Math."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Coelho E.M.M., Coelho H., Faria L., Ferreira M.D.P., Gravier S. and Klein S., On the oriented coloring of the disjoint union of graphs, in Combinatorial Algorithms \u2013 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5\u20137, 2021, Proceedings. Vol. 12757 of Lecture Notes in Computer Science, edited by Flocchini P. and Moura L.. Springer (2021) 194\u2013207.","DOI":"10.1007\/978-3-030-79987-8_14"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Culus J.-F. and Demange M., Oriented coloring: complexity and approximation, in International Conference on Current Trends in Theory and Practice of Computer Science. Springer (2006) 226\u2013236.","DOI":"10.1007\/11611257_20"},{"key":"R8","first-page":"125","volume":"9","author":"Erdos","year":"1964","journal-title":"Math. Inst. Hung. Acad. Sci."},{"key":"R9","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1080\/00029890.1966.11970749","volume":"73","author":"Harary","year":"1966","journal-title":"Am. Math. Monthly"},{"key":"R10","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1006\/jctb.1999.1945","volume":"78","author":"Havet","year":"2000","journal-title":"J. Comb. Theory Ser. B"},{"key":"R11","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0012-365X(03)00086-4","volume":"274","author":"Klostermeyer","year":"2004","journal-title":"Discret. Math."},{"key":"R12","doi-asserted-by":"crossref","first-page":"1489","DOI":"10.1007\/s00373-012-1202-y","volume":"29","author":"Marshall","year":"2013","journal-title":"Graphs Comb."},{"key":"R13","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.ipl.2008.04.007","volume":"108","author":"Ochem","year":"2008","journal-title":"Inf. Proc. Lett."},{"key":"R14","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0021-9800(70)80061-8","volume":"9","author":"Reid","year":"1970","journal-title":"J. Comb. Theory"},{"key":"R15","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF02986687","volume":"10","author":"S\u00e1nchez-Flores","year":"1994","journal-title":"Graphs Comb."},{"key":"R16","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s003730050025","volume":"14","author":"Sanchez-Flores","year":"1998","journal-title":"Graphs Comb."},{"key":"R17","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1002\/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G","volume":"25","author":"Sopena","year":"1997","journal-title":"J. Graph Theory"},{"key":"R18","doi-asserted-by":"crossref","first-page":"517","DOI":"10.7151\/dmgt.1624","volume":"32","author":"Sopena","year":"2012","journal-title":"Discuss. Math. Graph Theory"},{"key":"R19","doi-asserted-by":"crossref","first-page":"1993","DOI":"10.1016\/j.disc.2015.03.018","volume":"339","author":"Sopena","year":"2016","journal-title":"Discret. Math."},{"key":"R20","doi-asserted-by":"crossref","first-page":"385","DOI":"10.3390\/math8030385","volume":"8","author":"Sotskov","year":"2020","journal-title":"Mathematics"},{"key":"R21","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1080\/00029890.1959.11989405","volume":"66","author":"Stearns","year":"1959","journal-title":"Am. Math. Monthly"},{"key":"R22","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1090\/S0002-9947-1986-0837805-6","volume":"296","author":"Thomason","year":"1986","journal-title":"Trans. Am. Math. Soc."},{"key":"R23","first-page":"131","volume":"II","author":"Wagner","year":"2008","journal-title":"SOFSEM 2008"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024005\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T12:58:55Z","timestamp":1730984335000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024005"}},"subtitle":[],"editor":[{"given":"M.B.","family":"Campelo Neto","sequence":"first","affiliation":[]},{"given":"S.","family":"Klein","sequence":"additional","affiliation":[]},{"given":"I.","family":"Loiseau","sequence":"additional","affiliation":[]},{"given":"Y.","family":"Wakabayashi","sequence":"additional","affiliation":[]},{"given":"A.","family":"Weintraub","sequence":"additional","affiliation":[]},{"given":"V.","family":"dos Santos","sequence":"additional","affiliation":[]},{"given":"T.","family":"Liebling","sequence":"additional","affiliation":[]},{"given":"R.","family":"Mahjoub","sequence":"additional","affiliation":[]},{"given":"N.","family":"Maculan","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2024,1]]},"references-count":23,"journal-issue":{"issue":"1"},"alternative-id":["ro230159"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024005","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,1]]}}}