Mixed graph colorings

A mixed graphG π contains both undirected edges and directed arcs. Ak-coloring ofG π is an assignment to its vertices of integers not exceedingk (also called colors) 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 smallestk such thatG π admits ak-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. Copyright Physica-Verlag 1997