On Chromatic Number of Colored Mixed Graphs

摘要

An (m,n)-colored mixed graph G is a graph with its arcs having one of the m different colors and edges having one of the n different colors. A homomorphism f of an (m, n)-colored mixed graph G to an (m, n)-colored mixed graph H is a vertex mapping such that if uv is an arc (edge) of color c in G, then f(u)f(v) is an arc (edge) of color c in H. The (m,n)-colored mixed chromatic number X(m,n) (G) of an (m,n)-colored mixed graph G is the order (number of vertices) of a smallest homomorphic image of G. This notion was introduced by Nesetril and Raspaud (2000, J. Combin. Theory, Ser. B 80, 147-155). They showed that X(m,n)(G) ≤ k(2m + n)~(k-1) where G is a acyclic k-colorable graph. We prove the tightness of this bound. We also show that the acyclic chromatic number of a graph is bounded by k~2 + k~(2+[log_(2m+n) log_((2m+n)) k]) if its (m, n)-colored mixed chromatic number is at most k. Furthermore, using probabilistic method, we show that for connected graphs with maximum degree ∆ its (m, n)-colored mixed chromatic number is at most 2(∆ - 1)~(2m+n) (2m + n)~(∆-min(2m+n,3)+2) In particular, the last result directly improves the upper bound 2∆~22~∆ of oriented chromatic number of graphs with maximum degree ∆, obtained by Kostochka et al. (1997, J. Graph Theory 24, 331-340) to 2(∆ - 1)~22~∆. We also show that there exists a connected graph with maximum degree ∆ and (m, n)-colored mixed chromatic number at least (2m + n)~(∆/2).