Groupe d’études et de recherche en analyse des décisions


Mixed Graph Colorings

, et

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

Ce cahier a été révisé en avril 1996