Grafos sin 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(m1.41).La traza es cero si y sólo si el grafo no contiene triángulos.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.[1]​ Esta cota se pueden mejorar ligeramente: en cada grafo sin triángulos existe un conjunto independiente deCon probabilidad muy alta, este proceso produce un grafo con el número de independenciavé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.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.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[4]​ 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.