A step towards finding the analog of the Four-Color Theorem for $(n,m)$-graphs
<|reference_start|>A step towards finding the analog of the Four-Color Theorem for $(n,m)$-graphs: 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) \neq (0,1)$ and the bound is tight. This answers a naturally fundamental extremal question in the domain of homomorphisms of $(n,m)$-graphs and positively settles a recent conjecture by Bensmail \textit{et al.}~[Graphs and Combinatorics 2017]. Essentially, our result finds the clique number for planar $(n,m)$-graphs, which is a difficult problem except when $(n,m)=(0,1)$, answering a sub-question to finding the chromatic number for the family of planar $(n,m)$-graphs.<|reference_end|>
@article{bandopadhyay2024a,
    title={A step towards finding the analog of the Four-Color Theorem for
  $(n,m)$-graphs},
    author={Susobhan Bandopadhyay, Sagnik Sen and S Taruni},
    journal={arXiv preprint arXiv:2409.05678},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.05678},
    primaryClass={math.CO cs.DM}
}