Analogues of Cliques for (m, n)-Colored Mixed Graphs

作者：Bensmail Julien; Duffy Christopher; Sen Sagnik^*

来源：Graphs and Combinatorics, 2017, 33(4): 735-750.

DOI：10.1007/s00373-017-1807-2

• Colored mixed graphs
• Signed graphs
• Graph homomorphisms
• Chromatic number
• Clique number
• Planar graphs

An (m, n)-colored mixed graph is a mixed graph with arcs assigned one of m different colors and edges one of n different colors. A 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, denoted , of an (m, n)-colored mixed graph G is the order of a smallest homomorphic image of G. An (m, n)-clique is an (m, n)-colored mixed graph C with . Here we study the structure of (m, n)-cliques. We show that almost all (m, n)-colored mixed graphs are (m, n)-cliques, prove bounds for the order of a largest outerplanar and planar (m, n)-clique and resolve an open question concerning the computational complexity of a decision problem related to (0, 2)-cliques. Additionally, we explore the relationship between chi(1,0) and chi(0,2).

• 出版日期2017-7
• 单位INRIA