本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2020
摘要
Cographs are exactly the hereditarily well-colored graphs, i.e., the graphs for which a greedy vertex coloring of every induced subgraph uses only the minimally necessary number of colors χ(G). We show that greedy colorings are a special case of the more general hierarchical vertex colorings, which recently were introduced in 系統發育 combinatorics. Replacing cotrees by modular decomposition trees generalizes the concept of hierarchical colorings to arbitrary graphs. We show that every graph has a modularly-minimal coloring σ satisfying |σ(M)| = χ(M) for every strong module M of G. This, in particular, shows that modularly-minimal colorings provide a useful device to design efficient coloring algorithms for certain hereditary graph classes. For cographs, the hierarchical colorings coincide wit
※ 此為已發表論文，全文需透過期刊付費取得