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)$-圖族的色數的一個子問題。