En el área matemática de la teoría de grafos , el gráfico de Mycielskian o Mycielski de un grafo no dirigido es un grafo más grande formado a partir de él por 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.
Construcción
Deje que los n vértices del gráfico dado G sean v 1 , v 2 ,. . . , v n . El gráfico de Mycielski μ ( G ) contiene G en sí mismo como un 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 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 tanto, si G tiene n vértices y m aristas, μ ( G ) tiene 2 n +1 vértices y 3 m + n aristas.
Los únicos nuevos triángulos 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 ).
Ver que la construcción aumenta el número cromático , considere un k -coloring adecuado de; es decir, un mapeo con para vértices adyacentes x , y . Si tuvieramospara todo i , entonces podríamos definir una coloración adecuada ( k −1) de G mediante Cuándo , y de lo contrario. Pero esto es imposible para, entonces c debe usar todos los k colores para, y cualquier coloración adecuada del último vértice w debe usar un color adicional. Es decir,.
Mycielskianos iterados
Aplicar el Mycielskian repetidamente, 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 cíclico M 3 = C 5 y el gráfico de Grötzsch M 4 con 11 vértices y 20 aristas.
En general, la gráfica M i está libre de triángulos , ( i −1) - conectada a vértices e i - cromática . 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:
Propiedades
- Si G tiene un número cromático k , entonces μ ( G ) tiene un número cromático k + 1 ( Mycielski 1955 ).
- Si G no tiene triángulos , entonces también lo es μ ( G ) ( Mycielski 1955 ).
- De manera más general, si G tiene un número de camarilla ω ( G ), entonces μ ( G ) tiene un número de camarilla máximo (2, ω ( G )) ( Mycielski 1955 ).
- Si G es un gráfico de factor crítico , también lo es μ ( G ) ( Došlić 2005 ). En particular, cada gráfico M i para i ≥ 2 es un factor crítico.
- Si G tiene un ciclo hamiltoniano , también lo tiene μ ( G ) ( Fisher, McKenna y Boyer 1998 ).
- Si G tiene un número de dominación γ ( G ), entonces μ ( G ) tiene un número de dominación γ ( G ) +1. ( Fisher, McKenna y Boyer 1998 ).
Conos sobre gráficos
Stiebitz (1985) introdujo una generalización del Mycielskian, llamada cono sobre un gráfico, y Tardif (2001) y Lin et al. (2006) . En esta construcción, uno forma un gráfico Δ i ( G ) a partir de un gráfico G dado tomando el producto tensorial de los gráficos G × H , donde H es una ruta de longitud i con un bucle propio en un extremo, y luego colapsando en un solo supervertex todos los vértices asociados con el vértice de H en el extremo sin bucle de la ruta. El propio Mycielskian 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 lo hace cuando se aplica iterativamente a K 2 . Es decir, defina una secuencia de familias de grafos, llamados Mycielskianos generalizados, como
- ℳ (2) = { K 2 } y ℳ ( k +1) = {Δ i ( G ) | G ∈ ℳ ( k ), yo ∈ ℕ}.
Por ejemplo, ℳ (3) es la familia de ciclos impares. Entonces cada gráfica en ℳ ( k ) es k -cromática. La demostración 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 refuerza 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 al menos 2 r + 1, es decir, no contiene ciclos impares de longitud menos que 2 r + 1. Así, los Mycielskianos generalizados proporcionan una construcción simple de gráficos con un alto número cromático y una gran circunferencia impar.
Referencias
- Chvátal, Vašek (1974), "The minimalality of the Mycielski graph", Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973) , Lecture Notes in Mathematics, 406 , Springer-Verlag, págs. . 243–246.
- Došlić, Tomislav (2005), "Mycielskians and matchings", Discussiones Mathematicae Graph Theory , 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, empaquetamiento y particiones biclicuas de las gráficas de Mycielski", Discrete Applied Mathematics , 84 (1-3): 93-105, doi : 10.1016 / S0166-218X (97 ) 00126-1.
- Lin, Wensong; Wu, Jianzhuan; Lam, Peter Che Bor; Gu, Guohua (2006), "Varios parámetros de Mycielskians generalizados", Matemáticas aplicadas discretas , 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. Como lo cita Tardif (2001) .
- Tardif, C. (2001), "Números cromáticos fraccionarios de conos sobre gráficos", Journal of Graph Theory , 38 (2): 87–94, doi : 10.1002 / jgt.1025.
enlaces externos
- Weisstein, Eric W. "Gráfico Mycielski" . MathWorld .