Grafos sin triángulos
# Grafos sin triángulos

En Teoría de grafos, un grafo sin triángulos es un grafo no dirigido en el que no existen tres vértices que formen un triángulo de aristas. Grafos sin triángulos pueden ser equivalentemente definidos como grafos con número de clique <= 2, grafos con cintura >= 4, grafos sin ciclos de tamaño 3, o grafos localmente independientes.

Por el teorema de Turán, el grafo sin triángulos de N-vértice con el máximo número de aristas es un grafo bipartito completo en el que la cantidad de vértices en cada bipartición sea lo más similar posible.

## Problema de encontrar un triángulo

El problema encontrar un triángulo consiste en determinar si un grafo tiene o no triángulos. Cuando el grafo contiene un triángulo, los algoritmos a menudo devuelven como salida tres vértices que cumplen dicha condición. Es posible comprobar si un grafo con m aristas no contiene triángulos en tiempo $O(m^{1.41}).$ Otro enfoque es encontrar la traza de $A^3,$ donde A es la matriz de adyacencia del grafo. La traza es cero si y sólo si el grafo no contiene triángulos. Para grafos densos, es más eficiente utilizar este sencillo algoritmo que se basa en la multiplicación de matrices, ya que tiene un una complejidad temporal de $O(n^{2.373}),$ donde n es el número de vértices. Como Imrich, Klavžar y Mulder (1999) muestran, reconocer un grafo sin triángulos es equivalente en complejidad a reconocer la grafo mediano; sin embargo, los mejores algoritmos para la detección de la mediana de un grafo usan la detección de triángulos, no viceversa. El árbol de toma de decisión o la complejidad de la consulta del problema, donde las consultas son a un oráculo que almacena la matriz de adyacencia del grafo, es $T(n^2).$ Sin embargo, para los algoritmo cuánticos, la mejor cota es O(n), pero el mejor algoritmo hasta el momento, presentado por Belovs (2011) tiene cota $O(n^{1.29}).$

## Número de Independencia y Teoría de Ramsey

Un conjunto independiente de vn vértices en un grafo sin triángulos de n vértices es fácil de encontrar: o bien hay un vértice con mayor que vn vecinos (en cuyo caso los vecinos son un conjunto independiente ) o todos los vértices tienen menos de vn vecinos (en cuyo caso cualquier conjunto independiente maximal debe tener al menos vn vértices). Esta cota se pueden mejorar ligeramente: en cada grafo sin triángulos existe un conjunto independiente de $\Omega ({\sqrt {n\log n}})$ vértices, y en algunos grafos sin triángulos cada conjunto independiente tiene $O({\sqrt {n\log n}})$ vértices. Una forma de generar grafos sin triángulos en el que todos los conjuntos independientes son pequeños es el proceso de eliminación de triángulos en el que se genera un grafo sin triángulos maximal añadiendo iterativamente aristas elegidas al azar que no completen un triángulo. Con probabilidad muy alta, este proceso produce un grafo con el número de independencia $O({\sqrt {n\log n}})$. También es posible encontrar un Grafo regular con las mismas propiedades.

Estos resultados pueden interpretarse así mismo dando límites asintóticos a los números de Ramsey R(3,t) de la forma $\Theta ({\tfrac {t^{2}}{\log t}})$: si las aristas de un grafo completo con $\Omega ({\tfrac {t^{2}}{\log t}})$ vértices son coloreados de rojo o azul, entonces o bien el grafo rojo contiene un triángulo o, si no contiene triángulos, entonces debe tener un conjunto independiente de tamaño t correspondiente a un clique del mismo tamaño en el grafo azul.

## Coloración de grafos sin triángulos

Mucha de la investigación sobre grafos sin triángulos ha sido sobre coloración de grafos. Cada Grafo bipartito (es decir, cada grafo 2-coloreable) no contiene triángulos, y el teorema de Grötzsch establece que todo grafo planar sin triángulos es 3-coloreable. Sin embargo, los grafos sin triángulos no planares pueden requerir muchos más que tres colores.Mycielski (1955) definió una construcción, ahora llamado grafo de Mycielskian, , para la formación de un nuevo grafo sin triángulos a partir de otro grafo sin triángulos. Si un grafo tiene número cromático k, su Mycielskiano tiene número cromático k + 1, por lo que esta construcción puede ser utilizada para demostrar que una cantidad arbitraria de colores puede ser necesaria para colorear grafos sin triángulos no planares. En particular el grafo de Grötzsch, un grafo de 11 vértice formado por la aplicación repetida de la construcción de Mycielski, es un grafo sin triángulos que no es coloreable con menos de cuatro colores, y es el grafo más pequeño que cumple esta propiedad.Gimbel &Thomassen y (2000) and Nilli (2000) mostraron que el número de colores necesarios para colorear un grafo sin triángulos de m aristas es

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

y que existen grafos sin triángulos que tienen números cromáticos proporcionales a esta cota. También se han obtenido varios resultados relativos a la coloración mínima en grafos sin triángulos.Andrásfai, Erdős y Sós (1974) demostraron que cualquier grafo sin triángulos de n vértice en el que cada vértice tiene más de 2n/5 vecinos debe ser bipartito Este es el mejor resultado posible de este tipo, ya que el ciclo de tamaño 5 requiere de tres colores, pero tiene exactamente 2n/5 vecinos por vértice. Motivado por este resultado,Erdős y Simonovits (1973) conjeturó que cualquier grafo sin triángulos de n vértices en el que cada vértice tiene al menos n/3 3 vecinos puede ser coloreado con sólo tres colores, sin embargo,Häggkvist (1981) refuta esta conjetura encontrando un contraejemplo en el que cada vértice del grafo Grötzsch se sustituye por un conjunto independiente de tamaño cuidadosamente elegido.Jin (1995) demostró que cualquier grafo sin triángulos de nvértices en el que cada vértice tiene más de 10n/29 vecinos debe ser 3-coloreable, este es el mejor resultado posible de este tipo, ya que el grafo de Häggkvist requiere cuatro colores y exactamente 10n/29 vecinos por vértice. Por último,Brandt y Thomassé (2006) demostraron que cualquier grafo sin triángulos de n vértice en el que cada vértice tiene más de n/3 vecinos debe ser 4-coloreable. Resultados adicionales de este tipo no son posibles, ya que Hajnal encontró ejemplos de grafos sin triángulos con número cromático arbitrariamente grande y grado mínimo (1/3 − e)n para cualquier e > 0.

