Gráfico sin triángulos

En la teoría de grafos, un grafo sin triángulos es un grafo no dirigido en el que no hay tres vértices que formen un triángulo de aristas. Los gráficos sin triángulos también se pueden definir como gráficos con un número de clique ≤ 2, gráficos con circunferencia ≥ 4, gráficos sin 3 ciclos generados o como gráficos localmente independientes .

Según el teorema de Turan , un gráfico sin triángulos de n vértices con el máximo número de aristas es un gráfico bipartito completo en el que el número de vértices en cada parte del gráfico es lo más parecido posible.

Un gráfico con 2n vértices y sin triángulos debe tener menos aristas. $n^{2}+1$

El problema de encontrar triángulos

El problema de encontrar triángulos es el problema de determinar si un gráfico contiene triángulos o no. Si el gráfico contiene un triángulo, a menudo se le pide al algoritmo que genere tres vértices que formen un triángulo.

Es posible comprobar si un gráfico con m aristas tiene triángulos en el tiempo O( m 1.41 ). [1] Otro enfoque es encontrar la traza de la matriz A 3 , donde A es la matriz de adyacencia del gráfico. La traza es cero si y solo si no hay triángulos en el gráfico. Para gráficos densos, este algoritmo simple de multiplicación de matrices es más eficiente porque reduce la complejidad del tiempo a O( n 2.373 ), donde n es el número de vértices.

Como lo muestran Imrich, Klavžar y Mulder ( Imrich, Klavžar, Mulder 1999 ), el reconocimiento de gráficos sin triángulos es equivalente en complejidad al reconocimiento de gráficos medianos . Sin embargo, actualmente los mejores algoritmos de gráfico mediano utilizan el reconocimiento de triángulos como subrutina, y no al revés.

La complejidad del árbol de decisión o la complejidad de la consulta del problema, donde consultas al oráculo que recuerda las matrices de adyacencia del grafo, es igual a Θ( n 2 ). Sin embargo, para los algoritmos cuánticos, el mejor límite inferior es Ω( n ), pero el algoritmo más conocido tiene una estimación de O( n 1,29 ) ( Belovs 2011 ).

El número de independencia y la teoría de Ramsey

Un conjunto independiente de vértices en un grafo sin triángulos de n vértices es fácil de encontrar, ya sea que haya un vértice con más de vecinos (en cuyo caso los vecinos forman un conjunto independiente), o todos los vértices tienen menos de vecinos (en cuyo caso caso cualquier conjunto independiente más grande debe tener al menos vértices) [2] . Este límite se puede mejorar ligeramente: en cualquier gráfico sin triángulos hay un conjunto independiente con vértices, y en algunos gráficos sin triángulos, cualquier conjunto independiente tiene vértices. [3] Una forma de crear gráficos sin tegon en los que todos los conjuntos independientes son pequeños es el proceso sin triángulos [ 4] , que crea gráficos sin triángulos máximos al agregar secuencialmente bordes elegidos al azar, evitando la creación de triángulos. Con un alto grado de probabilidad, el proceso forma gráficos con número de independencia . También se pueden encontrar grafos regulares con las mismas propiedades. [5] ${\ sqrt {n}}$ ${\ sqrt {n}}$ ${\ sqrt {n}}$ ${\ sqrt {n}}$ $\Omega ({\sqrt {n\log n)))$ $O({\sqrt {n\log n)))$ $O({\sqrt {n\log n)))$

Estos resultados también pueden entenderse como el establecimiento de los límites asintóticos de los números de Ramsey R(3, t ) en la forma : si los bordes de un gráfico completo con vértices están coloreados en rojo y azul, entonces el gráfico rojo contiene un triángulo, o no hay triángulos en él, y entonces debe existir un conjunto independiente de tamaño t correspondiente a una camarilla de este tamaño en el gráfico azul. $\Theta ({\tfrac {t^{2)){\log t)))$ $\Omega ({\tfrac {t^{2)){\log t)))$

Colorear gráficos sin triángulos

Gran parte de la investigación sobre gráficos sin triángulos se ha centrado en la coloración de gráficos . Cualquier gráfico bipartito (es decir, cualquier gráfico bicolor) no tiene triángulos, y el teorema de Grötzsch establece que cualquier gráfico plano sin triángulos puede ser tricolor. [6] Sin embargo, los gráficos no planos sin triángulos pueden requerir más de tres colores.

Mycielski ( 1955 ) definió una construcción, ahora llamada Mycielskian , que forma un nuevo gráfico sin triángulos a partir de otro gráfico sin triángulos. Si un gráfico tiene un número cromático k , su mychelskiano tiene un número cromático k + 1, por lo que esta construcción se puede usar para mostrar que se puede requerir una cantidad arbitrariamente grande de colores para colorear un gráfico no plano sin triángulos. En particular, el gráfico de Grötzsch , un gráfico de 11 vértices formado al repetir la construcción de Mycielski, es un gráfico sin triángulos que no se puede colorear con menos de cuatro colores y es el gráfico más pequeño con estas propiedades. [7] Gimbel y Thomassen ( Gimbel, Thomassen & 2000 ) y ( Nilli 2000 ) demostraron que el número de colores necesarios para colorear cualquier gráfico de líneas m sin triángulos es

O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)

y hay gráficos sin triángulos que tienen números cromáticos proporcionales a este límite.

También hay algunos resultados sobre la conexión entre la coloración y el grado mínimo de gráficos sin triángulos. Andrásfai y Erdős ( Andrásfai, Erdős, Sós 1974 ) demostraron que cualquier grafo libre de triángulos de n vértices en el que cada vértice tiene más de un vecino debe ser bipartito. Este es el mejor resultado posible de este tipo, ya que el ciclo de 5 requiere tres colores, pero tiene exactamente vecinos para cada vértice. Animados por este resultado, Erdős y Simonovits ( Erdős, Simonovits 1973 ) conjeturaron que cualquier gráfico libre de triángulos con n vértices, en el que cada vértice tiene al menos vecinos, puede colorearse con solo tres colores. Sin embargo, Häggkvist ( 1981 ) refutó esta conjetura al presentar un contraejemplo en el que cada vértice del gráfico de Grötsch se reemplaza por un conjunto independiente de tamaño especialmente elegido. Jin ( Jin 1995 ) demostró que cualquier gráfico libre de triángulos de n vértices en el que cada vértice tiene más de un vecino puede tener 3 colores. Este es el mejor resultado de este tipo, ya que el gráfico de Haggquist requiere cuatro colores y tiene exactamente vecinos para cada vértice. Finalmente, Brandt y Thomassé ( Brandt, Thomassé 2006 ) demostraron que cualquier gráfico libre de triángulos de n -vértices en el que cualquier vértice tiene más de 4 vecinos se puede colorear con 4 colores. Resultados adicionales de este tipo son imposibles porque Hajnal [8] encontró ejemplos de gráficos sin triángulos con un número cromático arbitrariamente grande y un grado mínimo para cualquier . ${\ estilo de visualización 2n/5}$ ${\ estilo de visualización 2n/5}$ $n/3$ ${\ estilo de visualización 10n/29}$ ${\ estilo de visualización 10n/29}$ $n/3$ ${\ estilo de visualización (1/3-\ épsilon) n}$ $\epsilon > 0$

Enlaces

↑ Alon, Yuster, Zwick, 1994 .
↑ Boppana, Halldórsson, 1992 , basándose en la idea del algoritmo de aproximación anterior de Avi Wigderson ., p. 184.
↑ Kim, 1995 .
↑ Erdös, Suen, Winkler, 1995 ; Bowman, 2008
↑ Alon, Ben-Shimon, Krivelevich, 2008 .
↑ Grotzsch, 1959 ; ( Thomassen 1994 )).
↑ Chavatal, 1974 .
↑ véase Erdős, Simonovits, 1973 .

Fuentes

N. Alon, S. Ben-Shimon, M. Krivelevich. Una nota sobre los gráficos regulares de Ramsey. — 2008.
N. Alon, R. Yuster, U. Zwick. Actas del 2º Simposio Europeo sobre Algoritmos , Utrecht, Países Bajos. - 1994. - S. 354-364 .
B. Andrásfai, P. Erdős, VT Sos. Sobre la conexión entre el número cromático, la camarilla máxima y el grado mínimo de un gráfico // Matemáticas discretas . - 1974. - T. 8 , núm. 3 . — S. 205–218 . - doi : 10.1016/0012-365X(74)90133-2 .
T. Bohman. El proceso sin triángulos . — 2008.
Ravi Boppana, Magnús M. Halldorsson. Aproximación de conjuntos independientes máximos excluyendo subgrafos // BIT. - 1992. - T. 32 , núm. 2 . — S. 180–196 . -doi : 10.1007/ BF01994876 .
S. Brandt, S. Thomasse. Los gráficos sin triángulos densos son de cuatro colores: una solución al problema de Erdős-Simonovits. - 2006. Archivado el 4 de febrero de 2012.
N. Chiba, T. Nishizeki. Arboricidad y algoritmos de listado de subgrafos // SIAM Journal on Computing . - 1985. - T. 14 , núm. 1 . — Pág. 210–223 . -doi : 10.1137/ 0214017 .
Vasek Chavatal. Gráficos y combinatoria (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973). - Springer-Verlag, 1974. - T. 406. - S. 243-246. — (Apuntes de clase en Matemáticas).
P. Erdős, M. Simonovits. Sobre un problema de valencia en la teoría de grafos extremos // Matemáticas discretas. - 1973. - V. 5 , núm. 4 . — S. 323–334 . - doi : 10.1016/0012-365X(73)90126-X .
P. Erdős, S. Suen, P. Winkler. Sobre el tamaño de un gráfico máximo aleatorio // Estructuras aleatorias y algoritmos. - 1995. - T. 6 , núm. 2–3 . — S. 309–318 . -doi : 10.1002/ rsa.3240060217 .
John Gimbel, Carsten Thomassen. Colorear gráficos sin triángulos con tamaño fijo // Matemáticas discretas. - 2000. - T. 219 , núm. 1-3 . — S. 275–277 . -doi : 10.1016 / S0012-365X(00)00087-X .
H. Grotzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe. - 1959. - T. 8 . — S. 109–120 .
R. Haggkvist. Teoría de grafos (Cambridge, 1981). - 1981. - S. 89–99 .
Wilfried Imrich, Sandi Klavžar, Henry Martyn. Gráficos medianos y gráficos sin triángulos // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , núm. 1 . — págs. 111–118 . -doi : 10.1137/ S0895480197323494 .
A. Itai, M. Rodeh. Encontrar un circuito mínimo en un gráfico // SIAM Journal on Computing . - 1978. - V. 7 , núm. 4 . — S. 413–423 . -doi : 10.1137/ 0207033 .
Jin G. Gráficos cuatricromáticos sin triángulos // Matemáticas discretas. - 1995. - T. 145 , núm. 1-3 . — S. 151–170 . - doi : 10.1016/0012-365X(94)00063-O .
JH Kim. El número de Ramsey tiene orden de magnitud // Estructuras aleatorias y algoritmos. - 1995. - T. 7 , núm. 3 . — S. 173–207 . ${\ estilo de visualización R (3, t)}$ ${\tfrac {t^{2}}{\log t}}$
Frederic Magniez, Miklos Santha, Mario Szegedy. Algoritmos cuánticos para el problema del triángulo. — 2003.
J. Mycielski. Sur le coloriage des graphes // Colloq. Matemáticas.. - 1955. - T. 3 . — S. 161–162 .
A. Nilli. Gráficos sin triángulos con grandes números cromáticos // Matemáticas discretas. - 2000. - T. 211 , núm. 1–3 . — S. 261–262 . - doi : 10.1016/S0012-365X(99)00109-0 .
JB Shearer. Nota sobre el número de independencia de grafos sin triángulos // Matemáticas discretas. - 1983. - T. 46 , núm. 1 . — págs. 83–87 . - doi : 10.1016/0012-365X(83)90273-X .
C.Thomassen. Teorema de los 3 colores de Grötzsch // Journal of Combinatorial Theory, Serie B . - 1994. - T. 62 , núm. 2 . — S. 268–279 . -doi : 10.1006/ jctb.1994.1069 .
Aleksandrs Belovs. Programas de distribución para funciones con certificados 1 de tamaño constante. — 2011.