论文标题
完整的边缘置换图
Complete Edge-Colored Permutation Graphs
论文作者
论文摘要
我们将完整的边缘置换图的概念介绍为完整的图形，这些图是“经典”置换图的边缘偶会结合。我们表明，当且仅当每个单色子图的$ g $的每个单色子图是一个“经典”置换图时，$ g =（v，e）$是一个完整的边缘色排列图，而$ g $不包含〜$ 3 $不同颜色的三角形。使用模块化分解作为框架，我们证明了完整的边缘置换图表的特征是其强质质子模块，这些模块也诱导了完整的边缘色置换图。这导致$ \ Mathcal {O}（| V |^2）$ - 时间识别算法。此外，我们还表明，完整的边缘色置换图构成了所谓的符号超透明的超类，并且这种图的着色始终是加莱的着色。
We introduce the concept of complete edge-colored permutation graphs as complete graphs that are the edge-disjoint union of "classical" permutation graphs. We show that a graph $G=(V,E)$ is a complete edge-colored permutation graph if and only if each monochromatic subgraph of $G$ is a "classical" permutation graph and $G$ does not contain a triangle with~$3$ different colors. Using the modular decomposition as a framework we demonstrate that complete edge-colored permutation graphs are characterized in terms of their strong prime modules, which induce also complete edge-colored permutation graphs. This leads to an $\mathcal{O}(|V|^2)$-time recognition algorithm. We show, moreover, that complete edge-colored permutation graphs form a superclass of so-called symbolic ultrametrics and that the coloring of such graphs is always a Gallai coloring.
