Abstract:A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph $G$ is defined as the smallest order of a colored mixed graph $H$ such that there exists a (color preserving) homomorphism from $G$ to $H$. These notions were introduced by Ne\v {s}et\v {r}il and Raspaud in {Colored homomorphisms of colored mixed graphs}, J. Combin. Theory Ser. B {80} (2000), no. 1, 147--155, where the exact chromatic number of colored mixed trees was given. We prove here that this chromatic number is reached by the much simpler family of colored mixed paths. By means of this result we give lower bounds for the chromatic number of colored mixed partial $k$-trees, outerplanar and planar graphs.
Keywords: graph colorings, graph homomorphisms, colored mixed graphs
AMS Subject Classification: 05C15