WikiEdge:ArXiv-2409.05678v1/abs

编辑

• 标题：A step towards finding the analog of the Four-Color Theorem for $(n,m)$-graphs
• 中文标题：寻找 $(n,m)$-图的四色定理类比的一步
• 发布日期：2024-09-09T14:45:12+00:00
• 作者：Susobhan Bandopadhyay, Sagnik Sen, S Taruni
• 分类：math.CO, cs.DM
• 原文链接：http://arxiv.org/abs/2409.05678v1

摘要：一幅\textit{$(n,m)$-图} $G$ 是一种同时具有弧和边的图，其弧（或边）使用 $n$（或 $m$）种不同符号中的一种进行标记。一个\textit{$(n,m)$-完全图} $G$ 是一种没有环或多重边的 $(n,m)$-图，其底层图在识别任意一对顶点时会产生一个环或具有不同标签的平行邻接。我们证明了对于所有 $(n,m) \neq (0,1)$，一个平面 $(n,m)$-完全图的顶点数不能超过 $3(2n+m)^2+(2n+m)+1$，且该界限是紧的。这回答了 $(n,m)$-图同态领域中的一个自然基本极值问题，并积极解决了 Bensmail 等人于 2017 年提出的一个最近猜想。我们的结果实质上找到了平面 $(n,m)$-图的团数，这是一个困难的问题，除非 $(n,m)=(0,1)$，同时回答了寻找平面 $(n,m)$-图族的色数的一个子问题。