Complete Edge-Colored Permutation Graphs

Tom Hartmann, Max Bannach, Martin Middendorf, Peter F. Stadler, Nicolas Wieseke, 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 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 (|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.
PublikationsstatusVeröffentlicht - 15.04.2020


  • 409-01 Theoretische Informatik


Untersuchen Sie die Forschungsthemen von „Complete Edge-Colored Permutation Graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.