Harmonious Colorings of Digraphs

Abstract

Let $D$ be a directed graph with $n$ vertices and $m$ edges. A function $f:V(D)\to \{1,2,3,\dots ,k\}$, where $k\le n$, is said to be a harmonious coloring of $D$ if for any two edges $xy$ and $uv$ of $D$, the ordered pair $(f(x),f(y))\ne (f(u),f(v))$. If the pair $(i,i)$ is not assigned, then $f$ is said to be a proper harmonious coloring of $D$. The minimum $k$ is called the proper harmonious coloring number of $D$. We investigate the proper harmonious coloring number of various graphs, including unidirectional paths, unicycles, inward-spoken (outward-spoken) wheels, $n$-ary trees of different levels, and others.