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³, 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 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²). 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.

Véase también

• Triángulo monocromático problem, the problem of partitioning the edges of a given graph into two triangle-free graphs

Referencias

Notas

Fuentes

• Alon, N.; Ben-Shimon, S.; Krivelevich, M. (2008). «A note on regular Ramsey graphs». . .
• Alon, N.; Yuster, R.; Zwick, U. (1994), «Finding and counting given length cycles», Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, pp. 354-364 ..
• Andrásfai, B.; Erdős, P.; Sós, V. T. (1974), «On the connection between chromatic number, maximal clique and minimal degree of a graph», Discrete Mathematics (journal) 8 (3): 205-218, doi:10.1016/0012-365X(74)90133-2 

» ignorado (ayuda)..

• Bohman, T. (2008). «The triangle-free process». . .
• Boppana, Ravi; Halldórsson, Magnús M. (1992), «Approximating maximum independent sets by excluding subgraphs», BIT 32 (2): 180-196, MR 1172185, doi:10.1007/BF01994876 ..
• Brandt, S.; Thomassé, S. (2006), Dense triangle-free graphs are four-colorable: a solution to the Erdos-Simonovits problem, archivado desde el original el 4 de febrero de 2012, consultado el 24 de diciembre de 2013 ..
• Chiba, N.; Nishizeki, T. (1985), «Arboricity and subgraph listing algorithms», SIAM Journal on Computing 14 (1): 210-223, doi:10.1137/0214017 ..
• Chvátal, Vašek (1974), «The minimality of the Mycielski graph», Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Mathematics 406, Springer-Verlag, pp. 243-246 ..
• Erdős, P.; Simonovits, M. (1973), «On a valence problem in extremal graph theory», Discrete Mathematics 5 (4): 323-334, doi:10.1016/0012-365X(73)90126-X ..
• Erdős, P.; Suen, S.; Winkler, P. (1995), «On the size of a random maximal graph», Random Structures and Algorithms 6 (2–3): 309-318, doi:10.1002/rsa.3240060217 ..
• Gimbel, John; Thomassen, Carsten (2000), «Coloring triangle-free graphs with fixed size», Discrete Mathematics 219 (1-3): 275-277, doi:10.1016/S0012-365X(00)00087-X ..
• Grötzsch, H. (1959), «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 8: 109-120 ..
• Häggkvist, R. (1981), «Odd cycles of specified length in nonbipartite graphs», Graph Theory (Cambridge, 1981), pp. 89-99 ..
• Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), «Median graphs and triangle-free graphs», SIAM Journal on Discrete Mathematics 12 (1): 111-118, MR 1666073, doi:10.1137/S0895480197323494 ..
• Itai, A.; Rodeh, M. (1978), «Finding a minimum circuit in a graph», SIAM Journal on Computing 7 (4): 413-423, doi:10.1137/0207033 ..
• Jin, G. (1995), «Triangle-free four-chromatic graphs», Discrete Mathematics 145 (1-3): 151-170, doi:10.1016/0012-365X(94)00063-O ..
• Kim, J. H. (1995), «The Ramsey number $R(3,t)$ has order of magnitude ${\tfrac {t^{2}}{\log t}}$», Random Structures and Algorithms (3 edición) 7: 173-207 ..
• Magniez, Frederic; Santha, Miklos; Szegedy, Mario (2003). «Quantum Algorithms for the Triangle Problem». . .
• Mycielski, J. (1955), «Sur le coloriage des graphes», Colloq. Math. 3: 161-162 ..
• Nilli, A. (2000), «Triangle-free graphs with large chromatic numbers», Discrete Mathematics 211 (1–3): 261-262, doi:10.1016/S0012-365X(99)00109-0 ..
• Shearer, J. B. (1983), «Note on the independence number of triangle-free graphs», Discrete Mathematics 46 (1): 83-87, doi:10.1016/0012-365X(83)90273-X ..
• Thomassen, C. (1994), «Grötzsch's 3-color theorem», Journal of Combinatorial Theory, Series B 62 (2): 268-279, doi:10.1006/jctb.1994.1069 ..
• Belovs, Aleksandrs (2011). «Span Programs for Functions with Constant-Sized 1-certificates». . .

Enlaces externos

• «triangle-free», Information System on Graph Classes and their Inclusions .

Category:Graph families

• Datos: Q7840044