Gráfico sin triángulos - Triangle-free graph

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

Los gráficos sin triángulos con la mayor cantidad de aristas para sus vértices son gráficos bipartitos completos equilibrados . Muchos gráficos sin triángulos no son bipartitos, por ejemplo, cualquier gráfico de ciclo C _n para n impar   > 3.

Según el teorema de Turán , el gráfico sin triángulos de n -vértices con el número máximo de aristas es un gráfico bipartito completo en el que los números de vértices en cada lado de la bipartición son lo más iguales posible.

Problema de búsqueda de triángulos

El problema de encontrar triángulos es el problema de determinar si una gráfica está libre de triángulos o no. Cuando el gráfico contiene un triángulo, a menudo se requieren algoritmos para generar tres vértices que forman un triángulo en el gráfico.

Es posible probar si una gráfica con m aristas no tiene triángulos en el tiempo O ( m ^1,41 ). Otro enfoque es encontrar la traza de A ³ , donde A es la matriz de adyacencia del gráfico. La traza es cero si y solo si la gráfica no tiene triángulos. Para gráficos densos , es más eficiente usar este algoritmo simple que se basa en la multiplicación de matrices , ya que reduce la complejidad del tiempo a O ( n ^2.373 ), donde n es el número de vértices.

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 viceversa.

La complejidad del árbol de decisión o la complejidad de la consulta del problema, donde las consultas se dirigen a un oráculo que almacena la matriz de adyacencia de un gráfico, 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 ).

Número de independencia y teoría de Ramsey

Un conjunto independiente de √ n vértices en un gráfico sin triángulos de n -vértices es fácil de encontrar: o hay un vértice con más de √ n vecinos (en cuyo caso esos vecinos son un conjunto independiente) o todos los vértices tienen menos de √ n vecinos (en cuyo caso cualquier conjunto independiente máximo debe tener al menos √ n vértices). Este límite se puede ajustar ligeramente: en cada gráfico sin triángulos existe un conjunto independiente de vértices, y en algunos gráficos sin triángulos cada conjunto independiente tiene vértices. Una forma de generar gráficos sin triángulos en los que todos los conjuntos independientes son pequeños es el proceso sin triángulos en el que se genera un gráfico sin triángulos máximo agregando repetidamente aristas elegidas al azar que no completan un triángulo. Con alta probabilidad, este proceso produce una gráfica con número de independencia . También es posible encontrar gráficos regulares con las mismas propiedades. ${\ Displaystyle \ Omega ({\ sqrt {n \ log n}})}$${\ Displaystyle O ({\ sqrt {n \ log n}})}$${\ Displaystyle O ({\ sqrt {n \ log n}})}$

Estos resultados también se pueden interpretar como que dan límites asintóticos en los números de Ramsey R (3, t ) de la forma : si los bordes de un gráfico completo en los vértices son de color 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}})}$

Colorear gráficos sin triángulos

El gráfico de Grötzsch es un gráfico sin triángulos que no se puede colorear con menos de cuatro colores.

Gran parte de la investigación sobre gráficos sin triángulos se ha centrado en la coloración de gráficos . Cada gráfico bipartito (es decir, cada gráfico de 2 colores) no tiene triángulos, y el teorema de Grötzsch establece que cada gráfico plano sin triángulos puede tener 3 colores. Sin embargo, los gráficos sin triángulos no planos pueden requerir muchos más de tres colores.

La primera construcción de gráficos libres de triángulos con un número cromático arbitrariamente alto se debe a Tutte (escribiendo como Blanche Descartes ). Esta construcción se inició en el gráfico con una sola voz vértice e inductivamente construido a partir de la siguiente manera: Vamos a tener vértices, luego tomar un conjunto de vértices y para cada subconjunto de tamaño de agregar una copia de disjuntos y unirlo a una coincidencia. Del principio de casillero se deduce inductivamente que no es coloreable, ya que al menos uno de los conjuntos debe ser coloreado monocromáticamente si solo se nos permite usar k colores. Mycielski (1955) definió una construcción, ahora llamada Mycielskian , para formar un nuevo gráfico sin triángulos a partir de otro gráfico sin triángulos. Si una gráfica tiene un número cromático k , su Mycielskian tiene un número cromático k  + 1, por lo que esta construcción puede usarse para mostrar que puede ser necesario un número arbitrariamente grande de colores para colorear gráficos no planos sin triángulos. En particular, el gráfico de Grötzsch , un gráfico de 11 vértices formado por la aplicación repetida de 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 esta propiedad. Gimbel y Thomassen (2000) y Nilli (2000) demostraron que el número de colores necesarios para colorear cualquier gráfico sin triángulo de borde m es ${\ Displaystyle G_ {1}}$${\ Displaystyle G_ {k + 1}}$${\ Displaystyle G_ {k}}$${\ Displaystyle G_ {k}}$${\ Displaystyle n}$${\ Displaystyle Y}$${\ Displaystyle k (n-1) +1}$${\ Displaystyle X}$${\ Displaystyle Y}$${\ Displaystyle n}$${\ Displaystyle G_ {k}}$${\ Displaystyle X}$${\ Displaystyle G_ {k + 1}}$${\ Displaystyle k}$${\ Displaystyle X}$

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

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

También ha habido varios resultados que relacionan la coloración con un grado mínimo en gráficos sin triángulos. Andrásfai, Erdős & Sós (1974) demostraron que cualquier grafo sin triángulos de n -vértices en el que cada vértice tiene 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 & Simonovits (1973) conjeturaron que cualquier gráfico libre de triángulos de n -vértices en el que cada vértice tiene al menos n / 3 vecinos se puede colorear con sólo tres colores; sin embargo, Häggkvist (1981) refutó esta conjetura al encontrar un contraejemplo en el que cada vértice del gráfico de Grötzsch es reemplazado por un conjunto independiente de un tamaño cuidadosamente elegido. Jin (1995) mostró que cualquier gráfico sin triángulos de n -vértices en el que cada vértice tiene más de 10 n / 29 vecinos debe ser de 3 colores; este es el mejor resultado posible de este tipo, porque el gráfico 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 tiene más de n / 3 vecinos debe tener 4 colores. No es posible obtener resultados adicionales de este tipo, ya que Hajnal encontró ejemplos de gráficos sin triángulos con un número cromático arbitrariamente grande y un grado mínimo (1/3 - ε) n para cualquier ε> 0.

Ver también

• 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 sin triángulos infinitos que contiene todos los gráficos sin triángulos finitos como subgráficos 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 un número cromático${\ Displaystyle KG_ {3k-1, k}}$${\ Displaystyle k + 1}$
• Problema de 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 , en gráficos en los que cada borde pertenece exactamente a un triángulo

Referencias

Notas

Fuentes

enlaces externos

• "Graphclass: Triangle-free" , Sistema de información sobre clases de gráficos y sus inclusiones