论文标题
层次和微型顶点颜色
Hierarchical and Modularly-Minimal Vertex Colorings
论文作者
论文摘要
Cophaphs正是遗传上彩色的图形，即每个感应子仪器的贪婪顶点着色的图形仅使用最小必要数量的颜色$χ（g）$。我们表明，贪婪的着色是更通用的分层顶点着色的特殊情况，该颜色最近是在系统发育组合中引入的。通过模块化分解树代替Cotrees将分层色的概念推广到任意图。我们表明，每个图都有一个模块化的颜色$σ$满足$ |σ（m）| =χ（m）$，对于每个强模块$ m $ $ g $。特别是，这表明模块化最小的着色为某些遗传图类设计有效的着色算法提供了有用的设备。对于Cographs，分层着色与模块化最小的着色一致。作为副产品，我们获得了一种简单的线性时间算法来计算$ P_4 $ -SPARSE图的模块化最小颜色。
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 phylogenetic 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 with the modularly-minimal coloring. As a by-product, we obtain a simple linear-time algorithm to compute a modularly-minimal coloring of $P_4$-sparse graphs.
