Nous introduisons le concept de graphes de permutation complets de couleur d'arête comme des graphes complets qui sont l'union bord-disjonction de graphes de permutation « classiques ». Nous montrons qu'un graphe G=(V,E) est un graphe de permutation complet de couleur de bord si et seulement si chaque sous-graphe monochromatique de G est un graphe de permutation « classique » et G ne contient pas de triangle avec 3 couleurs différentes. En utilisant la décomposition modulaire comme cadre, nous démontrons que les graphes de permutation complets de couleur d'arête sont caractérisés en termes de leurs modules premiers forts, qui induisent également des graphes de permutation complets de couleur d'arête. Cela conduit à un algorithme de reconnaissance du temps O(|V|2). Nous montrons, en outre, que les graphes complets de permutation de couleur de bord forment une superclasse d'ultramétriques dits symboliques et que la coloration de tels graphes est toujours une coloration de Gallai.

Introducimos el concepto de gráficos de permutación completos de color de borde como gráficos completos que son la unión de bordes disjuntos de los gráficos de permutación "clásicos". Mostramos que un gráfico G=(V,E) es un gráfico de permutación de color de borde completo si y solo si cada subgráfico monocromático de G es un gráfico de permutación "clásico" y G no contiene un triángulo con 3 colores diferentes. Usando la descomposición modular como marco, demostramos que los gráficos de permutación completos de color de borde se caracterizan en términos de sus módulos primos fuertes, que inducen también gráficos de permutación completos de color de borde. Esto conduce a un algoritmo de reconocimiento de tiempo O(|V|2). Mostramos, además, que las gráficas de permutación completas de color de borde forman una superclase de las llamadas ultramétricas simbólicas y que la coloración de tales gráficas es siempre una coloración de Gallai.

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.

نقدم مفهوم الرسوم البيانية التبادلية الكاملة بلون الحافة كرسوم بيانية كاملة تمثل اتحادًا مفككًا للحافة للرسوم البيانية التبادلية "الكلاسيكية". نوضح أن الرسم البياني G=(V،E) هو رسم بياني كامل للتبديل بلون الحافة إذا وفقط إذا كان كل رسم بياني فرعي أحادي اللون لـ G هو رسم بياني للتبديل "كلاسيكي" و G لا يحتوي على مثلث بثلاثة ألوان مختلفة. باستخدام التحلل المعياري كإطار، نوضح أن الرسوم البيانية الكاملة ذات الألوان الحافة تتميز من حيث وحداتها الأولية القوية، والتي تحفز أيضًا الرسوم البيانية الكاملة ذات الألوان الحافة. يؤدي هذا إلى خوارزمية التعرف على الوقت O(| V|2). علاوة على ذلك، نظهر أن الرسوم البيانية الكاملة ذات الألوان الحافة تشكل طبقة فائقة من ما يسمى بالقياس الفائق الرمزي وأن تلوين مثل هذه الرسوم البيانية هو دائمًا تلوين Gallai.