Answers are grounded in this paper and cite their sources.
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 1 , G 2 was widely studied, but the disjoint union G 1 ∪ G 2 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 2 ( m ). Additionally, we established exact values of the union of one complete graph with one cycle and of one complete graph with a forest.
No takes yet. Share an insight, caveat, or question.
Coelho et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: