Coloración distintiva

En teoría de grafos , una coloración distintiva o etiquetado distintivo de un grafo consiste en asignar colores o etiquetas a los vértices del grafo, eliminando así todas las simetrías no triviales del mismo . La coloración no tiene por qué ser propia : se permite que los vértices adyacentes tengan el mismo color. Para el grafo coloreado, no debe existir ninguna correspondencia biunívoca entre los vértices que preserve tanto la adyacencia como la coloración. El número mínimo de colores en una coloración distintiva se denomina número distintivo del grafo.

Albertson y Collins (1996) introdujeron los sistemas de coloración y numeración distintivos , proporcionando el siguiente ejemplo ilustrativo, basado en un acertijo previamente formulado por Frank Rubin: «Supongamos que tenemos un llavero con llaves para diferentes puertas; cada llave abre solo una puerta, pero todas parecen indistinguibles. ¿Cuántos colores necesitamos para colorear los mangos de las llaves de forma que podamos identificarlas de manera única?» ^{[ 1 ]} Este ejemplo se resuelve utilizando un sistema de coloración distintivo para un grafo cíclico . Con dicho sistema, cada llave se identificará de forma única por su color y la secuencia de colores que la rodea. ^{[ 2 ]}

Un gráfico tiene un número distintivo uno si y solo si es asimétrico . ^{[ 3 ]} Por ejemplo, el gráfico de Frucht tiene una coloración distintiva con un solo color.

En un grafo completo , las únicas coloraciones distintivas asignan un color diferente a cada vértice. Porque, si a dos vértices se les asignara el mismo color, existiría una simetría que intercambiaría esos dos vértices, dejando el resto en su lugar. Por lo tanto, el número distintivo del grafo completo K _n es n . Sin embargo, el grafo obtenido a partir de K _n al adjuntar un vértice de grado uno a cada vértice de K _n tiene un número distintivo significativamente menor, a pesar de tener el mismo grupo de simetría: tiene una coloración distintiva con${\displaystyle \lceil {\sqrt {n}}\rceil }$colores, obtenidos al usar un par de colores ordenados diferente para cada par de un vértice K _n y su vecino adjunto. ^{[ 2 ]}

Para un grafo cíclico de tres, cuatro o cinco vértices, se necesitan tres colores para construir una coloración distintiva. Por ejemplo, cada coloración de dos colores de un ciclo de cinco tiene una simetría de reflexión . En cada uno de estos ciclos, asignar un color único a cada uno de dos vértices adyacentes y usar el tercer color para todos los vértices restantes da como resultado una coloración distintiva de tres colores. Sin embargo, los ciclos de seis o más vértices tienen coloraciones distintivas con solo dos colores. Es decir, el rompecabezas del llavero de Frank Rubin requiere tres colores para anillos de tres, cuatro o cinco llaves, pero solo dos colores para seis o más llaves o para dos llaves. ^{[ 2 ]} Por ejemplo, en el anillo de seis llaves que se muestra, cada llave se puede distinguir por su color y por la longitud o longitudes de los bloques adyacentes de llaves de color opuesto: hay solo una llave para cada combinación de color de llave y longitudes de bloques adyacentes.

Los grafos hipercubo exhiben un fenómeno similar al de los grafos cíclicos. Los grafos hipercubo bidimensionales y tridimensionales (el ciclo de 4 dimensiones y el grafo de un cubo, respectivamente) tienen como número distintivo tres. Sin embargo, cada grafo hipercubo de dimensión superior tiene como número distintivo solo dos. ^{[ 4 ]}

El grafo de Petersen tiene un número distintivo  3. Sin embargo, aparte de este grafo y los grafos completos, todos los grafos de Kneser tienen un número distintivo  2. ^{[ 5 ]} De manera similar, entre los grafos de Petersen generalizados , solo el propio grafo de Petersen y el grafo del cubo tienen un número distintivo  3; el resto tienen un número distintivo  2. ^{[ 6 ]}

Los números distintivos de árboles , grafos planares y grafos de intervalos se pueden calcular en tiempo polinomial . ^{[ 7 ] [ 8 ] [ 9 ]}

La complejidad exacta del cálculo de los números distintivos no está clara, ya que está estrechamente relacionada con la complejidad aún desconocida del isomorfismo de grafos . Sin embargo, se ha demostrado que pertenece a la clase de complejidad AM . ^{[ 10 ]} Además, comprobar si el número cromático distintivo es como máximo tres es NP-difícil , ^{[ 9 ]} y comprobar si es como máximo dos es "al menos tan difícil como el automorfismo de grafos, pero no más difícil que el isomorfismo de grafos". ^{[ 11 ]}

Una coloración de un grafo dado es distintiva para ese grafo si y solo si es distintiva para el grafo complemento . Por lo tanto, cada grafo tiene el mismo número distintivo que su complemento. ^{[ 2 ]}

Para cada grafo G , el número distintivo de G es como máximo proporcional al logaritmo del número de automorfismos de G. Si los automorfismos forman un grupo abeliano no trivial , el número distintivo es dos, y si forman un grupo diedral, entonces el número distintivo es como máximo tres. ^{[ 2 ]}

Para cada grupo finito , existe un grafo con ese grupo como su grupo de automorfismos, con número distintivo dos. ^{[ 2 ]} Este resultado extiende el teorema de Frucht que establece que todo grupo finito puede realizarse como el grupo de simetrías de un grafo.

Una coloración distintiva propia es una coloración distintiva que también es una coloración propia: cada par de vértices adyacentes tienen colores diferentes. El número mínimo de colores en una coloración distintiva propia de un grafo se denomina número cromático distintivo del grafo. ^{[ 12 ]}