Equitable oriented coloring.

In this paper, we consider equitable oriented colorings of graphs. Such coloring is a natural combination of two well‐known colorings: oriented coloring and equitable coloring. An oriented k $k$‐coloring ϕ $\phi $ of an oriented graph G→ $\overrightarrow{G}$ is an arc‐preserving homomorphism from G→ $\overrightarrow{G}$ into an oriented graph H→ $\overrightarrow{H}$ on k $k$ vertices, or colors. We say that the coloring is equitable if for every two colors c1,c2∈V(H→) ${c}_{1},{c}_{2}\in V(\overrightarrow{H})$, we have ∣∣ϕ−1(c1)∣−∣ϕ−1(c2)∣∣≤1 $| | {\phi }^{-1}({c}_{1})| -| {\phi }^{-1}({c}_{2})| | \le 1$. This paper presents the following results: we show that there is an undirected graph G $G$ such that every orientation of G $G$ is equitably oriented 5‐colorable, and we show that there is an orientation of G $G$ that cannot be colored with six colors. In other words, there is a gap in the set of numbers of colors that can be used for equitable oriented coloring of G $G$. Additionally, we concentrate on paths and show that there is an orientation of a path that requires four colors to be equitably oriented colorable. On the other hand, we show that every orientation of any path is equitably oriented k $k$‐colorable, for every k≥5 $k\ge 5$. [ABSTRACT FROM AUTHOR]