The Set Chromatic Number of a Digraph

Abstract

Given a (not necessarily proper) coloring of a digraph $c:V(D)\to N$, let $OC(v)$ denote the set of colors assigned to the out-neighbors of $v$. Similarly, let $IC(v)$ denote the set of colors assigned to the in-neighbors of $v$. Then $c$ is a set coloring of $D$ provided $(u,v)\in A(D)$ implies $OC(u)\ne OC(v)$. Analogous to the set chromatic number of a graph given by Chartrand, $et$ $al.$ $[3]$, we define ${\chi }_s(D)$ as the minimum number of colors required to produce a set coloring of $D$. We find bounds for ${\chi }_s(D)$ where $D$ is a digraph and where $D$ is a tournament. In addition we consider a second set coloring, where $(u,v)\in A(D)$ implies $OC(u)\ne IC(v)$.