2018/10/12 by Sandip Das, Soumen Nandi, Das, Sandip +5
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1810.05503
openalex publication_date 2018/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An (m, n)-colored mixed graph is a graph having arcs of m different colors and edges of n different colors. A graph homomorphism 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 also an arc (edge) of color c. The (m, n)-colored mixed chromatic number of an (m, n)-colored mixed graph G, introduced by Nešetřil and Raspaud [J. Combin. Theory Ser. B 2000] is the order (number of vertices) of the smallest homomorphic image of G. Later Bensmail, Duffy and Sen [Graphs Combin. 2017] introduced another parameter related to the (m, n)-colored mixed chromatic number, namely, the (m, n)-relative clique number as the maximum cardinality of a vertex subset which, pairwise, must have distinct images with respect to any colored homomorphism. In this article, we study the (m, n)-relative clique number for the family of subcubic graphs, graphs with maximum degree Δ, planar graphs and triangle-free planar graphs and provide new improved bounds in each of the cases. In particular, for subcubic graphs we provide exact value of the parameter.