En el área matemática de la teoría de grafos , el gráfico mycielskiano o mycielskiano de un gráfico no dirigido es un gráfico más grande formado a partir de él mediante una construcción de Jan Mycielski (1955). La construcción conserva la propiedad de no tener triángulos pero aumenta el número cromático ; Al aplicar la construcción repetidamente a un gráfico inicial sin triángulos, Mycielski demostró que existen gráficos sin triángulos con un número cromático arbitrariamente grande.
Sean v 1 , v 2 , los n vértices del gráfico dado G. . . , v n . El gráfico 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 vi de G , y un vértice adicional 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 gráfico 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 k -coloración adecuada de ; es decir, un mapeo para vértices adyacentes x , y . Si tuviéramos para todo i , entonces podríamos definir una coloración ( k −1) adecuada de G mediante cuando y de otra manera. Pero esto es imposible para , por lo que c debe usar todos los k colores para , y cualquier coloración adecuada del último vértice w debe usar un color adicional. Eso es, .
La aplicación repetida del método mycielskiano, comenzando con el gráfico de un borde, produce una secuencia de gráficos M i = μ( M i −1 ), a veces llamados gráficos de Mycielski. Los primeros gráficos de esta secuencia son el gráfico M 2 = K 2 con dos vértices conectados por una arista, el gráfico de ciclo M 3 = C 5 y el gráfico de Grötzsch M 4 con 11 vértices y 20 aristas.
En general, el gráfico M i no tiene triángulos , ( i −1) está conectado a vértices y i es cromático . El número de vértices en M i para i ≥ 2 es 3 × 2 i −2 − 1 (secuencia A083329 en el 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 gráfico, y Tardif (2001) y Lin et al la estudiaron más a fondo. (2006). En esta construcción, se forma un gráfico a partir de un gráfico G dado tomando el producto tensorial G × H , donde H es un camino de longitud i con un bucle automático en un extremo, y luego colapsando en un solo supervértice todos los vértices. asociado con el vértice de H en el extremo sin bucle del camino. El propio mycielskiano se puede formar 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, definir una secuencia de familias de grafos, llamados Mycielskianos generalizados, como
Por ejemplo, ℳ(3) es la familia de ciclos impares. Entonces cada gráfico 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 los gráficos de Kneser . La propiedad libre de triángulos se fortalece de la siguiente manera: si solo se aplica la construcción del cono Δ i para i ≥ r , entonces el gráfico resultante tiene una circunferencia impar de al menos 2 r + 1, es decir, no contiene ciclos impares de longitud menor. que 2 r + 1. Por lo tanto, los mycielskianos generalizados proporcionan una construcción simple de gráficos con un número cromático alto y una circunferencia impar alta.
