Micielskiano

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 no tener triángulos pero aumenta el número cromático; al aplicar la construcción repetidamente a un grafo inicial sin triángulos, Mycielski demostró que existen grafos sin triángulos con un número cromático arbitrariamente grande.

Sean los n vértices del grafo dado G v₁, v₂,... 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_iv_j de G, el grafo de Mycielski incluye dos aristas, u_iv_j y v_iu_j.

Por lo tanto, si G tiene n vértices y m aristas, μ(G) tiene 2n+1 vértices y 3m+n aristas.

Los únicos triángulos nuevos en μ(G) son de la forma v_iv_ju_k, donde v_iv_jv_k es un triángulo en G. Por lo tanto, si G no tiene triángulos, tampoco lo tiene μ(G).

Para ver que la construcción aumenta el número cromático ${\displaystyle \chi (G)=k}$, considerar un adecuado k-coloración de ${\displaystyle \mu (G){-}\{w\}}$; es decir, una asignación ${\displaystyle C:\{v_{1},\ldotsv_{n},u_{1},\ldotsu_{n}\to \{1,2,\ldotsk}$ con ${\displaystyle c(x)\neq c(y)}$ para vértices adyacentes x,Sí.. Si lo hubiéramos hecho ${\displaystyle c(u_{i})\in \{1,2,\ldotsk{-}1\}}$ para todos i, entonces podríamos definir un adecuado (k1) -coloración de G por ${\displaystyle c'\!(v_{i})=c(u_{i}}$ cuando ${\displaystyle c(v_{i})=k}$, y ${\displaystyle c'\!(v_{i})=c(v_{i}}$ de lo contrario. Pero esto es imposible ${\displaystyle \chi (G)=k}$, entonces c debe usar todo k colores para ${\displaystyle \{u_{1},\ldotsu_{n}}}$, y cualquier coloración adecuada del último vértice w Debe usar un color extra. Eso es, ${\displaystyle \chi (\mu (G)=k{+}1}$.

Si se aplica el método de Mycielski repetidamente, comenzando con el grafo de una arista, se obtiene 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₂ = K₂ con dos vértices conectados por una arista, el grafo cíclico M₃ = C₅ y el grafo de Grötzsch M₄ con 11 vértices y 20 aristas.

En general, el grafo M_i no tiene triángulos, es conexo por (i−1) vértices y es i-cromático. El número de vértices en M_i para i ≥ 2 es 3 × 2ⁱ⁻² − 1 (secuencia A083329 en la OEIS), mientras que el número de aristas para i = 2, 3,... es:

1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355,... A122695 en el OEIS).

• Si G tiene número cromático k, entonces μ(G) tiene número cromático k + 1 (Mycielski 1955).
• Si G es libre de triángulo, entonces es μ(G(Mycielski 1955).
• Más generalmente, si G tiene número de camarillasG), entonces μ(G) tiene el número de camarilla del máximo entre 2 y ω(G). (Mycielski 1955)
• Si G es un gráfico factor-crítico, entonces es μ(G) (Došlić 2005). En particular, cada gráfico M_i para i ≥ 2 es factor crítico.
• Si G tiene un ciclo Hamiltoniano, entonces también μ(G) (Fisher, McKenna & Boyer 1998).
• Si G tiene número de dominación γ(G), entonces μ(G) tiene el número de dominación γ(G)+1 (Fisher, McKenna & Boyer 1998).

Stiebitz (1985) introdujo una generalización del Mycielskian, llamada cono sobre un gráfico, y estudió posteriormente Tardif (2001) y Lin et al. (2006). En esta construcción se forma un gráfico ${\displaystyle \Delta _{i}(G)}$ de un gráfico dado G tomando el producto tensor G × H, donde H es un camino de longitud i con un self-loop en un extremo, y luego colapsando en un solo supervertex todos los vértices asociados con el vértice de H en el extremo no abierto del camino. El propio Mycielskiano se puede formar de esta manera como μ(G) = Δ₂()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₂. Es decir, defina una secuencia de familias de grafos, llamadas Mycielskianas generalizadas, como

M(2) = {K₂} y M(k+1) = {${\displaystyle \Delta _{i}(G)}$ Silencio G zioDtk), yo , ${\displaystyle \mathbb {N}$}.

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 de ausencia de triángulos se refuerza 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 2r + 1, es decir, no contiene ciclos impares de longitud menor que 2r + 1. Por lo tanto, los mycielskianos generalizados proporcionan una construcción simple de grafos con un número cromático alto y una circunferencia impar alta.

• Chvátal, Vašek (1974), "La minimalidad del gráfico Mycielski", Gráficos y Combinatorios (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Notas de conferencias en matemáticas, vol. 406, Springer-Verlag, págs. 243 a 246.
• Došlić, Tomislav (2005), "Mycielskians and matchings", Discusiones Gráfico Mathematicae Teoría, 25 (3): 261–266, doi:10.7151/dmgt.1279, MR 2232992.
• Fisher, David C.; McKenna, Patricia A.; Boyer, Elizabeth D. (1998), "Hamiltonicidad, diámetro, dominación, embalaje y particiones biblicas de los gráficos de Mycielski", Discreta Matemáticas aplicadas, 84 (1–3): 93–105, doi:10.1016/S0166-218X(97)00126-1.
• Lin, Wensong; Wu, Jianzhuan; Lam, Peter Che Bor; Gu, Guohua (2006), "Parámetros totales de los micielskianos generalizados", Discreta Matemáticas aplicadas, 154 (8): 1173–1182, doi:10.1016/j.dam.2005.11.001.
• Mycielski, Jan (1955), "Sur le coloriage des graphes" (PDF), Colloq. Matemáticas., 3 (2): 161-162, doi:10.4064/cm-3-2-161-162.
• Stiebitz, M. (1985), Beiträge zur Theorie der färbungskritschen Graphen, Tesis de Habilitación, Technische Universität Ilmenau. As cited by Tardif (2001).
• Tardif, C. (2001), "Números cromáticos tradicionales de conos sobre gráficos", Journal of Graph Theory, 38 (2): 87–94, doi:10.1002/jgt.1025.

• Weisstein, Eric W. "Mycielski Graph". MathWorld.