The Set Chromatic Number of a Digraph

L. J. Langley1, S. K. Merz2
1Department of Mathematics, University of the Pacific, Stockton, CA, 95211, U.S.A.
2University of the Pacific

Abstract

Given a (not necessarily proper) coloring of a digraph \( c:V(D)\rightarrow {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) \neq 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) \neq IC(v)\).

Keywords: set coloring, chromatic number, digraph, tournament