Relative Clique Number of Planar Signed Graphs

摘要

A signed relative clique number of signed graph (where edges are assigned positive or negative signs) is the size of a largest subset X of vertices such that every two vertices are either adjacent or are part of a 4-cycle with an odd number of negative edges. The signed relative clique number is sandwiched between two other parameters of signed graphs, namely, the signed absolute clique number and the signed chromatic number, all three notions defined in [R. Naserasr, E. Rollova, and E. Sopena. Homomorphisms of signed graphs. Journal of Graph Theory, 2014]. Thus, together with a result from [P. Ochem, A. Pinlou, and S. Sen. Homomorphisms of signed planar graphs. arXiv preprint arXiv: 1401.3308, 2014.], the lower bound of 8 and upper bound of 40 has already been proved for the signed relative clique number of the family of planar graphs. Here we improve the upper bound to 15. Furthermore, we determine the exact values of signed relative clique number of the families of outerplanar graphs and triangle-free planar graphs.