En el área matemática de la teoría de grafos , el grafo mycielskiano o grafo mycielskiano de un grafo no dirigido es un grafo más grande formado a partir de él mediante una construcción de Jan Mycielski (1955). La construcción conserva la propiedad de ser libre de triángulos pero aumenta el número cromático ; al aplicar la construcción repetidamente a un grafo de partida libre de triángulos, Mycielski demostró que existen grafos libres de triángulos con un número cromático arbitrariamente grande.
Sean los n vértices del grafo dado G v 1 , v 2 , . . . , v n . El grafo de Mycielski μ( G ) contiene al propio G como subgrafo, junto con n +1 vértices adicionales: un vértice u i correspondiente a cada vértice v i de G , y un vértice extra w . Cada vértice u i está conectado por una arista a w , de modo que estos vértices forman un subgrafo en forma de estrella K 1, n . Además, para cada arista v i v j de G , el grafo de Mycielski incluye dos aristas, u i v j y v i u j .
Por lo tanto, si G tiene n vértices y m aristas, μ( G ) tiene 2 n +1 vértices y 3 m + n aristas.
Los únicos triángulos nuevos en μ( G ) son de la forma v i v j u k , donde v i v j v k es un triángulo en G . Por lo tanto, si G no tiene triángulos, también lo es μ( G ).
Para ver que la construcción aumenta el número cromático , considere una coloración k propia de ; es decir, una aplicación con para los vértices adyacentes x , y . Si tuviéramos para todo i , entonces podríamos definir una coloración ( k −1) propia de G por cuando , y en caso contrario. Pero esto es imposible para , por lo que c debe usar todos los k colores para , y cualquier coloración propia del último vértice w debe usar un color adicional. Es decir, .
La aplicación repetida del mycielskiano, comenzando con el grafo de una arista, produce una secuencia de grafos M i = μ( M i −1 ), a veces llamados grafos de Mycielski. Los primeros grafos de esta secuencia son el grafo M 2 = K 2 con dos vértices conectados por una arista, el grafo cíclico M 3 = C 5 y el grafo de Grötzsch M 4 con 11 vértices y 20 aristas.
En general, el grafo M i no tiene triángulos , ( i −1) es conexo por vértices y es i cromático . El número de vértices en M i para i ≥ 2 es 3 × 2 i −2 − 1 (secuencia A083329 en la OEIS ), mientras que el número de aristas para i = 2, 3, . . . es:
Stiebitz (1985) introdujo una generalización del mycielskiano, llamada cono sobre un grafo, que fue estudiada en profundidad por Tardif (2001) y Lin et al. (2006). En esta construcción, se forma un grafo a partir de un grafo G dado tomando el producto tensorial G × H , donde H es un camino de longitud i con un bucle propio en un extremo, y luego colapsando en un único supervértice todos los vértices asociados con el vértice de H en el extremo sin bucle del camino. El mycielskiano en sí puede formarse de esta manera como μ( G ) = Δ 2 ( G ).
Si bien la construcción del cono no siempre aumenta el número cromático, Stiebitz (1985) demostró que sí lo hace cuando se aplica iterativamente a K 2 . Es decir, define una secuencia de familias de grafos, llamadas Mycielskianas generalizadas, como
Por ejemplo, ℳ(3) es la familia de ciclos impares. Entonces cada grafo en ℳ( k ) es k -cromático. La prueba utiliza métodos de combinatoria topológica desarrollados por László Lovász para calcular el número cromático de grafos de Kneser . La propiedad libre de triángulos se refuerza entonces de la siguiente manera: si uno solo aplica la construcción del cono Δ i para i ≥ r , entonces el grafo resultante tiene una circunferencia impar de al menos 2 r + 1, es decir, no contiene ciclos impares de longitud menor que 2 r + 1. Así, los mycielskianos generalizados proporcionan una construcción simple de grafos con alto número cromático y alta circunferencia impar.
