Abstract
Let \(\overrightarrow{G} = (V, A)\) be an oriented graph and G the underlying graph of \(\overrightarrow{G}\). An oriented k-coloring of \(\overrightarrow{G}\) is a partition of V into k subsets such that there are no two adjacent vertices belonging to the same subset, and all the arcs between a pair of subsets have the same orientation. The oriented chromatic number \(\chi _o({\overrightarrow{G}})\) of \(\overrightarrow{G}\) is the smallest k, such that \({\overrightarrow{G}}\) admits an oriented k-coloring. The oriented chromatic number of G, denoted by \(\chi _o(G)\), is the maximum of \(\chi _o(\overrightarrow{G})\) for all orientations \(\overrightarrow{G}\) of G. Oriented chromatic number of product of graphs were widely studied, but the disjoint union has not being considered. In this article we study oriented coloring for the disjoint union of graphs. We establish the exact values of the union: of two complete graphs, of one complete with a forest graph, and of one complete and one cycle. Given a positive integer k, we denote by \(\mathcal {C}\mathcal {N}_k\) the class of graphs G such that \(\chi _o(G) \le k\). We use those results to characterize the class of graphs \(\mathcal {CN}_3\). We evaluate, as far as we know for the first time, the value of \(\chi _o(W_n)\) and we yield with this value an upper bound for the union of one complete and one wheel graph \(W_n\).
The authors are grateful to FAPEG, FAPERJ, CNPq and CAPES for their support of this research.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aravind, N.R., Narayanan, N., Subramanian, C.R.: Oriented colouring of some graph products. Discuss. Math. Graph Theory 31(4), 675–686 (2011). https://doi.org/10.7151/dmgt.1572
Coelho, H., Faria, L., Gravier, S., Klein, S.: Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs. Discret. Appl. Math. 198, 109–117 (2016). https://doi.org/10.1016/j.dam.2015.06.023
Culus, J.-F., Demange, M.: Oriented coloring: complexity and approximation. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 226–236. Springer, Heidelberg (2006). https://doi.org/10.1007/11611257_20
Dybizbanski, J., Nenca, A.: Oriented chromatic number of cartesian products and strong products of paths. Discuss. Math. Graph Theory 39(1), 211–223 (2019). https://doi.org/10.7151/dmgt.2074
Fertin, G., Raspaud, A., Roychowdhury, A.: On the oriented chromatic number of grids. Inf. Proc. Lett. 85(5), 261–266 (2003). https://doi.org/10.1016/S0020-0190(02)00405-2
Ganian, R., Hliněný, P.: New results on the complexity of oriented colouring on restricted digraph classes. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorný, J., Rumpe, B. (eds.) SOFSEM 2010. LNCS, vol. 5901, pp. 428–439. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11266-9_36
Klostermeyer, W., MacGillivray, G.: Homomorphisms and oriented colorings of equivalence classes of oriented graphs. Discret. Math. 274(1–3), 161–172 (2004). https://doi.org/10.1016/S0012-365X(03)00086-4
Marshall, T.H.: Homomorphism bounds for oriented planar graphs of given minimum girth. Graphs Comb. 29(5), 1489–1499 (2013). https://doi.org/10.1007/s00373-012-1202-y
Ochem, P., Pinlou, A.: Oriented colorings of partial 2-trees. Inf. Proc. Lett. 108(2), 82–86 (2008). https://doi.org/10.1016/j.ipl.2008.04.007
Raspaud, A., Sopena, E.: Good and semi-strong colorings of oriented planar graphs. Inf. Proc. Lett. 51(4), 171–174 (1994). https://doi.org/10.1016/0020-0190(94)00088-3
Sopena, É.: The chromatic number of oriented graphs. J. Graph Theory 25(3), 191–205 (1997). https://doi.org/10.1002/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G
Sopena, É.: Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs. Discuss. Math. Graph Theory 32(3), 517–533 (2012). https://doi.org/10.7151/dmgt.1624
Sopena, É.: Homomorphisms and colourings of oriented graphs: An updated survey. Discret. Math. 339(7), 1993–2005 (2016). https://doi.org/10.1016/j.disc.2015.03.018
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Coelho, E.M.M., Coelho, H., Faria, L., Ferreira, M.d.P., Gravier, S., Klein, S. (2021). On the Oriented Coloring of the Disjoint Union of Graphs. In: Flocchini, P., Moura, L. (eds) Combinatorial Algorithms. IWOCA 2021. Lecture Notes in Computer Science(), vol 12757. Springer, Cham. https://doi.org/10.1007/978-3-030-79987-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-79987-8_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-79986-1
Online ISBN: 978-3-030-79987-8
eBook Packages: Computer ScienceComputer Science (R0)