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)\mathit{\text{-colored}}\mathit{\text{mixed}}\mathit{\text{chromatic}}\mathit{\text{number}}$ ${\chi }_{(m,n)}(G)$ of an $(m,n)$-colored mixed graph $G$ is the order (number of vertices) of the smallest homomorphic image of $G$. This notion was introduced by Ne\v{s}et\v{r}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 $k$-acyclic colorable graph. We proved the tightness of this bound. We also showed that the acyclic chromatic number of a graph is bounded by $k^2 + k^{2 + \lceil log_{(2m+n)} log_{(2m+n)} k \rceil}$ifits$(m,n)$-colored mixed chromatic number is at most $k$. Furthermore, using probabilistic method, we showed that for graphs with maximum degree $\mathrm{\Delta }$ its $(m,n)$-colored mixed chromatic number is at most $2(\mathrm{\Delta }-1{)}^{2m+n}(2m+n{)}^{\mathrm{\Delta }-1}$. In particular, the last result directly improves the upper bound $2{\mathrm{\Delta }}^2{2}^{\mathrm{\Delta }}$ of oriented chromatic number of graphs with maximum degree $\mathrm{\Delta }$, obtained by Kostochka, Sopena and Zhu (1997, J. Graph Theory 24, 331–340) to $2(\mathrm{\Delta }-1{)}^2{2}^{\mathrm{\Delta }-1}$. We also show that there exists a graph with maximum degree $\mathrm{\Delta }$ and $(m,n)$-colored mixed chromatic number at least $(2m+n{)}^{\mathrm{\Delta }\mathrm{/}2}$.