A mixed graph GÅ𝒪 contains both undirected edges and directed arcs. A k-coloring of GÅ𝒪 is an assignment to its vertices of integers not exceeding k (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 smallest k such that GÅ𝒪 admits a k-coloring. To the best of the present knowledge it is studied here for the first time. The authors present bounds of γÅ𝒪(G), µdiscuss algorithms to find this quantity for trees and general graphs, and report computational experience.
