Large planar $(n,m)$-cliques

Abstract

An \textit{$(n,m)$-graph} $G$ is a graph having both arcs and edges, and its arcs (resp., edges) are labeled using one of the $n$ (resp., $m$) different symbols. An \textit{$(n,m)$-complete graph} $G$ is an $(n,m)$-graph without loops or multiple edges in its underlying graph such that identifying any pair of vertices results in a loop or parallel adjacencies with distinct labels. We show that a planar $(n,m)$-complete graph cannot have more than $3(2n+m{)}^2+(2n+m)+1$ vertices, for all $(n,m)\ne (0,1)$ and that the bound is tight. This positively settles a conjecture by Bensmail \textit{et al.}~[Graphs and Combinatorics 2017].

12 pages