| Autor: |
Hartmann, Tom, Bannach, Max, Middendorf, Martin, Stadler, Peter F., Wieseke, Nicolas, Hellmuth, Marc |
| Rok vydání: |
2020 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
