On the oriented coloring of the disjoint union of graphs^*

¹ Instituto de Informática, Universidade Federal de Goiás, Goiânia, Brazil
² Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Rio de Janeiro, Brazil
³ CNRS – Institut Fourier, Université Grenoble Alpes, Grenoble, France
⁴ Instituto de Matemática, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil

^** Corresponding author: mateus_ferreira@ufg.br

Received: 2 March 2023
Accepted: 23 December 2023

Abstract

Let G⃗ = (V, A) be an oriented graph and G the underlying graph of G⃗. An oriented k-coloring of G⃗ is a partition of V into k 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 k such that G⃗ admits an oriented k-coloring is the oriented chromatic number χ_o(G⃗) = k of G⃗. The oriented chromatic number χ_o(G) of the undirected graph G is the maximum of χ_o(G⃗) for all orientations G⃗ of G. Oriented chromatic number of the product of two graphs G₁, G₂ was widely studied, but the disjoint union G₁ ∪ G₂ 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 K_n and K_m with n ≥ m, there is a real number α ∈ (1, 3) such that χ_o(K_n ∪ K_m) = n + m − α log₂(m). Additionally, we established exact values of the union of one complete graph with one cycle and of one complete graph with a forest.