Hartmann, Tom; Max Bannach; Martin Middendorf; Peter F. Stadler; Nicolas Wieseke and Marc Hellmuth
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 com- plete 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 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.