本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
Cographs 正是遺傳性良好著色圖，即每個導出子圖的貪婪頂點著色僅使用最小必要數量的顏色 χ(G) 的圖。我們證明貪婪著色是更一般的分層頂點著色的特例，最近在系統發育組合學中引入了這種著色。用模組化分解樹取代協樹將分層著色的概念推廣到任意圖。我們證明每個圖都有一個模最小著色 σ 滿足 |σ(M)| = χ(M) 對於 G 的每個強模組 M。這特別顯示模最小著色提供了一個有用的工具來為某些遺傳圖類設計有效的著色演算法。對於 cographs，分層著色與模組化最小著色一致。作為副產品，我們獲得了一個簡單的線性時間演算法來計算 P4 稀疏圖的模組化最小著色。