Gráfico sin triángulos

En el área matemática de 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 grafos sin triángulos pueden definirse de manera equivalente como grafos con un número de clique  ≤ 2, grafos con circunferencia  ≥ 4, grafos sin ciclos de 3 inducidos o grafos localmente independientes .

Por el teorema de Turán , el grafo libre de triángulos de n vértices con el máximo número de aristas es un grafo bipartito completo en el que los números de vértices en cada lado de la bipartición son lo más iguales posibles.

El problema de búsqueda o detección de triángulos consiste en determinar si un gráfico no tiene triángulos o no. Cuando el gráfico contiene un triángulo, a menudo se requieren algoritmos para generar tres vértices que formen un triángulo en el gráfico.

Es posible probar si un grafo con aristas está libre de triángulos en el tiempo donde el oculta factores subpolinómicos. Aquí está el exponente de la multiplicación rápida de matrices ; ^[1] de lo que se deduce que la detección de triángulos se puede resolver en el tiempo . Otro enfoque es encontrar la traza de A ³ , donde A es la matriz de adyacencia del grafo. La traza es cero si y solo si el grafo está libre de triángulos. Para grafos densos , es más eficiente usar este algoritmo simple que nuevamente se basa en la multiplicación de matrices, ya que reduce la complejidad temporal a , donde es el número de vértices.${\estilo de visualización m}$${\displaystyle {\tilde {O}}{\bigl (}m^{2\omega /(\omega +1)}{\bigr )}}$${\displaystyle {\tilde {O}}}$${\estilo de visualización \omega}$ ${\displaystyle \omega <2.372}$$Estilo de visualización O(m^{1.407})}$${\displaystyle O(n^{\omega })}$${\estilo de visualización n}$

Incluso si se descubrieran algoritmos de multiplicación de matrices con tiempo , los mejores límites temporales que se podrían esperar de estos enfoques son o . En la complejidad de grano fino , la hipótesis del triángulo disperso es una suposición de dureza computacional no probada que afirma que no es posible ningún límite temporal de la forma , para cualquier , independientemente de las técnicas algorítmicas que se utilicen. Esta, y la hipótesis del triángulo denso correspondiente de que no es posible ningún límite temporal de la forma , implican límites inferiores para varios otros problemas computacionales en optimización combinatoria y geometría computacional . ^[2]${\displaystyle O(n^{2})}$${\displaystyle O(m^{4/3})}$${\displaystyle O(n^{2})}$${\displaystyle O(m^{4/3-\delta })}$${\displaystyle \delta >0}$${\displaystyle O(n^{\omega -\delta })}$

Como demostraron Imrich, Klavžar y Mulder (1999), el reconocimiento de gráficos sin triángulos es equivalente en complejidad al reconocimiento de gráficos medianos ; sin embargo, los mejores algoritmos actuales para el reconocimiento de gráficos medianos utilizan la detección de triángulos como una subrutina en lugar de lo contrario.

La complejidad del árbol 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 de un grafo, es Θ( n ² ) . Sin embargo, para los algoritmos cuánticos , el límite inferior más conocido es Ω( n ) , pero el algoritmo más conocido es O ( n ^5/4 ) . ^[3]

Un conjunto independiente de vértices (donde es la función de suelo ) en un grafo libre de triángulos con n vértices es fácil de encontrar: o bien hay un vértice con al menos vecinos (en cuyo caso esos vecinos son un conjunto independiente) o todos los vértices tienen estrictamente menos de vecinos (en cuyo caso cualquier conjunto independiente maximal debe tener al menos vértices). ^[4] Este límite se puede ajustar ligeramente: en cada grafo libre de triángulos existe un conjunto independiente de vértices, y en algunos grafos libres de triángulos cada conjunto independiente tiene vértices. ^[5] Una forma de generar grafos libres de triángulos en los que todos los conjuntos independientes son pequeños es el proceso libre de triángulos ^[6] en el que se genera un grafo libre de triángulos maximal añadiendo repetidamente aristas elegidas al azar que no completan un triángulo. Con alta probabilidad, este proceso produce un grafo con número de independencia . También es posible encontrar grafos regulares con las mismas propiedades. ^[7]${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor \cdot \rfloor}$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \Omega ({\sqrt {n\log n}})}$${\displaystyle O({\sqrt {n\log n}})}$${\displaystyle O({\sqrt {n\log n}})}$

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

Gran parte de la investigación sobre grafos sin triángulos se ha centrado en la coloración de los grafos . Todo grafo bipartito (es decir, todo grafo que se pueda colorear con dos colores) no tiene triángulos, y el teorema de Grötzsch establece que todo grafo plano sin triángulos puede tener tres colores. ^[8] Sin embargo, los grafos no planos sin triángulos pueden requerir muchos más de tres colores.

La primera construcción de grafos libres de triángulos con un número cromático arbitrariamente alto se debe a Tutte (escribiendo como Blanche Descartes ^[9] ). Esta construcción comenzó a partir del grafo con un solo vértice, digamos , y se construyó inductivamente a partir de lo siguiente: sea que tenga vértices, luego tome un conjunto de vértices y para cada subconjunto de de tamaño agregue una copia disjunta de y únala a con un correspondiente. Del principio del palomar se sigue inductivamente que no es coloreable, ya que al menos uno de los conjuntos debe estar coloreado monocromáticamente si solo se nos permite usar k colores. Mycielski (1955) definió una construcción, ahora llamada Mycielskian , para formar un nuevo grafo libre de triángulos a partir de otro grafo libre de triángulos. Si un grafo tiene número cromático k , su Mycielskian tiene número cromático k  + 1, por lo que esta construcción puede usarse para mostrar que pueden necesitarse cantidades arbitrariamente grandes de colores para colorear grafos libres de triángulos no planos. En particular, el grafo de Grötzsch , un grafo de 11 vértices formado por la aplicación repetida de la construcción de Mycielski, es un grafo sin triángulos que no se puede colorear con menos de cuatro colores, y es el grafo más pequeño con esta propiedad. ^[10] Gimbel & Thomassen (2000) y Nilli (2000) demostraron que la cantidad de colores necesarios para colorear cualquier grafo sin triángulos de m aristas es$Estilo de visualización G_{1}$$Estilo de visualización G_{k+1}$$Estilo de visualización Gk$$Estilo de visualización Gk$${\estilo de visualización n}$${\estilo de visualización Y}$${\displaystyle k(n-1)+1}$${\estilo de visualización X}$${\estilo de visualización Y}$${\estilo de visualización n}$$Estilo de visualización Gk$${\estilo de visualización X}$$Estilo de visualización G_{k+1}$${\estilo de visualización k}$${\estilo de visualización X}$

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

y que existen grafos libres de triángulos que tienen números cromáticos proporcionales a este límite.

También se han obtenido varios resultados que relacionan la coloración con el grado mínimo en grafos sin triángulos. Andrásfai, Erdős y Sós (1974) demostraron que cualquier grafo sin triángulos de n vértices en el que cada vértice tenga más de 2 n /5 vecinos debe ser bipartito. Este es el mejor resultado posible de este tipo, ya que el ciclo de 5 requiere tres colores pero tiene exactamente 2 n /5 vecinos por vértice. Motivados por este resultado, Erdős y Simonovits (1973) conjeturaron que cualquier grafo sin triángulos de n vértices en el que cada vértice tenga al menos n /3 vecinos puede colorearse con solo tres colores; sin embargo, Häggkvist (1981) refutó esta conjetura al encontrar un contraejemplo en el que cada vértice del grafo de Grötzsch se reemplaza por un conjunto independiente de un tamaño cuidadosamente elegido. Jin (1995) demostró que cualquier grafo sin triángulos de n vértices en el que cada vértice tenga más de 10 n /29 vecinos debe ser 3-coloreable; este es el mejor resultado posible de este tipo, porque el grafo de Häggkvist requiere cuatro colores y tiene exactamente 10 n /29 vecinos por vértice. Finalmente, Brandt y Thomassé (2006) demostraron que cualquier grafo sin triángulos de n vértices en el que cada vértice tenga más de n /3 vecinos debe ser 4-coloreable. No son posibles resultados adicionales de este tipo, ya que Hajnal ^[11] encontró ejemplos de grafos sin triángulos con un número cromático arbitrariamente grande y un grado mínimo (1/3 − ε) n para cualquier ε > 0.

• Gráfico de Andrásfai , una familia de gráficos circulantes sin triángulos con diámetro dos
• Gráfico de Henson , un gráfico infinito sin triángulos que contiene todos los gráficos finitos sin triángulos como subgrafos inducidos
• Gráfico de desplazamiento , una familia de gráficos sin triángulos con un número cromático arbitrariamente alto
• El gráfico de Kneser no tiene triángulos y tiene número cromático.$Estilo de visualización KG_{3k-1,k}$${\estilo de visualización k+1}$
• Problema del triángulo monocromático , el problema de dividir los bordes de un gráfico dado en dos gráficos sin triángulos.
• Problema de Ruzsa-Szemerédi , sobre grafos en los que cada arista pertenece exactamente a un triángulo

• "Graphclass: triangle-free", Sistema de información sobre clases de grafos y sus inclusiones