Estoy tratando de encontrar una reducción de tiempo polinomial desde el isomorfismo del gráfico de color al isomorfismo del gráfico regular. Al realizar una búsqueda sobre este problema, encontré este artículo y parece que el teorema 1 es la solución que estoy buscando, sin embargo, no lo entiendo completamente. ¿Podría alguien explicar cómo funciona la reducción?
Respuesta
¿Demasiados anuncios?
"un polinomio reducción del tiempo de la gráfica de colores isomorfismo para el gráfico regular isomorfismo" ....
la siguiente prueba es debido a Pascal Schweitzer,
Teorema 1 (reducción de color de incoloro gráfico isomorfismo). El gráfico isomorfismo problema de coloreado de grafos polinomio de tiempo se reduce a la incoloro gráfico isomorfismo problema.
Prueba: Supongamos que se nos da dos de color de los gráficos $G_1, G_2$ $n$ vértices. Si los conjuntos de colores utilizado para los gráficos no son iguales, podemos reducir el problema a un Ninguna instancia de incoloro gráfico de isomorfismo, es decir, algunos fijos par de no isomorfos gráficos.
Si los gráficos utilizan el mismo conjunto de colores, nos adjuntar para cada vértice de un árbol de raíces, cuyo tipo de isomorfismo es en uno-a-uno correspondencia con el color del vértice: se elige un canónica bijection de el color establecido para el conjunto de árboles de raíces para que cada la hoja está a la altura de la $⌈log2(n)⌉$, y que tiene un grado máximo de $3$. Tal un bijection está dada por el siguiente método: el número de los colores con números enteros en $\{0, . . . , n − 1\}$. A un color con codificación binaria $ a_0 a_1 . . . a_{⌈log2 n−1⌉}$ le asigna el árbol para que cada vértice en la altura de la $i$ tiene exactamente $a_i + 1$ niños. Obtenemos dos nuevos gráficos $G′_ 1$, $G′ _2$ del tamaño en la mayoría de los $O(n^2)$. Por inducción sobre la altura, es fácil muestran que estos nuevos grafos son isomorfos si y sólo si el original los gráficos son.
