ON THE DICHROMATIC INDEX OF A DIGRAPH

Abstract

Let D be a digraph. The arc (u, v) is adjacent to the arc (w, x) if v = w. Let r(D) be the smallest number of arc colors so that no two adjacent arcs have the same color. Let G be the underlying graph of D and let x(G) be its usual chromatic number. We extend a lower bound of Lovász for r(D) by proving that