A Study of Harmonious and Complete Colorings of Digraphs

Abstract

In this research work, we have extended the concept of harmonious colorings, complete colorings and set colorings of graphs to directed graphs. A harmonious coloring of any digraph D is an assignment of colors to the vertices of D and the color of an arc is defined to be the ordered pair of colors to its end vertices such that all arc colors are distinct. The proper harmonious coloring number is the least number of colors needed in such a coloring. Also, we obtain a lower bound for the proper harmonious coloring of any digraphs and regular digraphs and investigate the proper harmonious coloring number of some classes of digraphs. A complete coloring of a digraph D is a proper vertex coloring of D such that, for any ordered pair of colors, there is at least one arc of D whose endpoints are colored with this pair of colors. The achromatic number of D is the maximum number of colors in a proper complete coloring of D. We obtain an upper bound for the achromatic number of digraphs. Also, we find the achromatic number of some classes of digraphs. We have extended the concept of set colorings of graphs to set colorings of digraphs. We have given some necessary conditions for a digraph to admit a strong set coloring (proper set coloring). We will characterize strongly (properly) set colorable digraphs. Also, we find the construction of strongly (properly) set colorable directed caterpillars.