2020/04/15 by Hartmann, Tom, Bannach, Max, Middendorf, Martin +3
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2004.07118
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 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.