Colored homomorphisms of colored mixed graphs

The homomorphisms of oriented or undirected graphs, the oriented chromatic number, the relationship between acyclic coloring number and oriented chrom atic number, have been recently studied. improving and combining earlier te chniques of N. Alon and T. H. Marshall (1998, J. Algebraic Combin. 8, 5-13) and A. Raspaud and E. Sopena (1994, Inform. Process. Lett. 51, 171-174) we prove here a general result about homomorphisms of colored mixed graphs wh ich implies all these earlier results about planar graphs. We also determin e the exact chromatic number of colored mixed trees. For this, we introduce the notion of colored homomorphism for mixed graphs containing both colore d arcs and colored edges. (C) 2000 Academic Press.