Group for Research in Decision Analysis


Mixed Graph Colorings

, , and

A mixed graph G contains both undirected edges and directed arcs. A k-coloring of G is an assignment to its vertices (also called colors) of integers not exceeding k so that the endvertices of an edge have different colors and the tail of any arc has a smaller color than its head. The chromatic number (G) of a mixed graph is the smallest k such that G admits a k-coloring. To the best of our knowledge it is studied here for the first time. We present bounds of (G), discuss algorithms to find this quantity for trees and general graphs, and report computational experience.

, 19 pages

This cahier was revised in April 1996