2015/08/28 by Sandip Das, Soumen Nandi, Das, Sandip +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #melanin and skin pigmentation
paper · pdf · doi:10.48550/arxiv.1508.07222
openalex publication_date 2015/08/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 χ(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šetřil and Raspaud (2000, J. Combin. Theory, Ser. B 80, 147--155). They showed that χ(m,n)(G) ≤ 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 k2 + 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 showed that for graphs with maximum degree Δ its (m,n)-colored mixed chromatic number is at most 2(Δ-1)2m+n (2m+n)Δ-1. In particular, the last result directly improves the upper bound 2Δ2 2Δ of oriented chromatic number of graphs with maximum degree Δ, obtained by Kostochka, Sopena and Zhu (1997, J. Graph Theory 24, 331--340) to 2(Δ-1)2 2Δ-1. We also show that there exists a graph with maximum degree Δ and (m,n)-colored mixed chromatic number at least (2m+n)Δ/ 2.