On relative clique number of colored mixed graphs
share
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.
READ FULL TEXT