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 \((\textit{m,n})\) -colored mixed chromatic number \(\chi _{(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 Nešetřil and Raspaud (2000, J. Combin. Theory, Ser. B 80, 147–155). They showed that \(\chi _{(m,n)}(G) \le 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 + \lceil \log _{(2m+n)} \log _{(2m+n)} k \rceil }\) 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 \(\varDelta \) its (m, n)-colored mixed chromatic number is at most \(2(\varDelta -1)^{2m+n} (2m+n)^{\varDelta -\min (2m+n, 3)+2}\). In particular, the last result directly improves the upper bound \(2\varDelta ^2 2^{\varDelta }\) of oriented chromatic number of graphs with maximum degree \(\varDelta \), obtained by Kostochka et al. (1997, J. Graph Theory 24, 331–340) to \(2(\varDelta -1)^2 2^{\varDelta }\). We also show that there exists a connected graph with maximum degree \(\varDelta \) and (m, n)-colored mixed chromatic number at least \((2m+n)^{\varDelta /2}\).