Coloración exacta

En teoría de grafos , una coloración exacta es una coloración de vértices (propia) en la que cada par de colores aparece en exactamente un par de vértices adyacentes. Es decir, es una partición de los vértices del grafo en conjuntos independientes disjuntos , de tal manera que, para cada par de conjuntos independientes distintos en la partición, existe exactamente una arista con extremos en cada conjunto. ^{[ 1 ] [ 2 ]}

Todo grafo completo K _n de n vértices tiene una coloración exacta con n colores, obtenida al asignar un color distinto a cada vértice. Todo grafo con una coloración exacta de n colores puede obtenerse como un desprendimiento de un grafo completo, un grafo obtenido a partir del grafo completo dividiendo cada vértice en un conjunto independiente y reconectando cada arista incidente al vértice con exactamente uno de los miembros del conjunto independiente correspondiente. ^{[ 1 ] [ 2 ]}

Cuando k es un número impar , un camino o ciclo con${\displaystyle {\tbinom {k}{2}}}$Las aristas tienen una coloración exacta, obtenida al formar una coloración exacta del grafo completo K _k y luego encontrar un recorrido euleriano de este grafo completo. Por ejemplo, un camino con tres aristas tiene una coloración completa de 3 colores. ^{[ 2 ]}

Las coloraciones exactas están estrechamente relacionadas con las coloraciones armónicas (coloraciones en las que cada par de colores aparece como máximo una vez) y las coloraciones completas (coloraciones en las que cada par de colores aparece al menos una vez). Claramente, una coloración exacta es una coloración que es a la vez armónica y completa. Un grafo G con n vértices y m aristas tiene una k -coloración armónica si y solo si${\displaystyle m\leq {\tbinom {k}{2}}}$y el gráfico formado a partir de G añadiendo${\displaystyle {\tbinom {k}{2}}-m}$Los bordes aislados tienen una coloración exacta. Un grafo G con los mismos parámetros tiene una coloración k completa si y solo si${\displaystyle m\geq {\tbinom {k}{2}}}$y existe un subgrafo H de G con una k -coloración exacta en el que cada arista de G − H tiene extremos con coloraciones diferentes. La necesidad de la condición sobre las aristas de G − H se muestra con el ejemplo de un ciclo de cuatro vértices, que tiene un subgrafo con una 3-coloración exacta (el camino de tres aristas) pero no tiene una 3-coloración completa en sí mismo. ^{[ 2 ]}    

Determinar si un grafo dado tiene una coloración exacta es un problema NP-completo , incluso si el grafo es un árbol . ^{[ 1 ] [ 3 ]} Sin embargo, el problema puede resolverse en tiempo polinomial para árboles de grado acotado . ^{[ 1 ] [ 4 ]}