Coloración distintiva
En la teoría de grafos , un color distintivo o un etiquetado distintivo de un gráfico es una asignación de colores o etiquetas a los vértices del gráfico que destruye todas las simetrías no triviales del gráfico . La coloración no necesita ser una coloración adecuada : se permite dar el mismo color a los vértices adyacentes. Para el gráfico coloreado, no debería existir ningún mapeo uno a uno de los vértices entre sí que conserve tanto la adyacencia como el color. El número mínimo de colores en una coloración distintiva se denomina número distintivo del gráfico.
Albertson & Collins (1996) introdujeron colores distintivos y números distintivos , quienes proporcionaron el siguiente ejemplo motivador, basado en un rompecabezas formulado previamente por Frank Rubin: "Suponga que tiene un anillo de llaves para diferentes puertas; cada llave solo abre una puerta , pero todos parecen indistinguibles para usted. ¿Cuántos colores necesita para colorear las manijas de las llaves de tal manera que pueda identificar cada llave de manera única? [1] Este ejemplo se resuelve usando un color distintivo para un gráfico de ciclo . Con tal coloración, cada tecla se identificará de forma única por su color y la secuencia de colores que la rodean. [2]
Un gráfico tiene el número uno distintivo 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 gráfico completo , los únicos colores distintivos 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 gráfico obtenido de K n al unir un vértice de grado uno a cada vértice de K n tiene un número distintivo significativamente más pequeño, a pesar de tener el mismo grupo de simetría: tiene una coloración distintiva con colores, obtenida usando un par ordenado diferente de colores para cada par de un vértice K ny su vecino anexo. [2]
Para un gráfico de ciclo de tres, cuatro o cinco vértices, se necesitan tres colores para construir una coloración distintiva. Por ejemplo, cada dos colores de un ciclo de cinco tiene una simetría de reflexión. En cada uno de estos ciclos, la asignación de un color único a cada uno de los dos vértices adyacentes y el uso del 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 colores distintivos con solo dos colores. Es decir, el 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 colores opuestos: solo hay una llave para cada combinación de color de llave y longitudes de bloques adyacentes. .
Los gráficos de hipercubo exhiben un fenómeno similar a los gráficos de ciclo. Los gráficos de hipercubo de dos y tres dimensiones (el de 4 ciclos y el gráfico de un cubo, respectivamente) tienen el número tres distintivo. Sin embargo, cada gráfico de hipercubo de mayor dimensión tiene un número distintivo solo dos. [4]
