Posted inNEWS
平衡染色數與 Hadwiger 類猜想:結構結果與分佈式系統中的應用
背景與問題定義在圖論與系統設計交叉的領域中,透過圖著色(graph coloring)來解決衝突資源分配或程序調度是一項常見做法。傳統染色數 χ(G) 代表將頂點分組,確保每個子群不會在同一顏色內產生相鄰邊;然而當系統邊帶有「正/負」關係(如微服務間的支援與相斥互動)時,傳統模型不足以描述負向循環(negative cycle)所帶來的邏輯死結風險。近年來,研究者引入簽名圖(signed graph)的概念,並定義平衡染色數 χ_b(G,σ) 為將頂點分為若干部分,保證每個部分所誘導子圖皆不含負環。此概念延伸自四染色定理及其在 Planar Graph 的應用,為更複雜系統拓撲提供衡量指標。簽名版 Hadwiger 猜想與等價性2023 年,arXiv:2308.01242v2 提出一個簽名圖版本的 Hadwiger 猜想:若簽名圖 \hat{G} 不含負自環也不存在 \tilde{K_t} 小極大化(minor),則其平衡染色數至多 t−1。研究團隊證明此猜想實際上與經典 Hadwiger 猜想等價(Hadwiger, 1943),並與 Odd Hadwiger Conjecture(Gerards & Seymour,…