Grafos sem triangulos

Na área de Teoria dos grafos da matemática, um grafo sem triângulos ou grafo livre de triângulos é um grafo não-direcionado no qual nenhum conjunto de três vértices forma um grafo triângulo de arestas. Grafos sem triângulos podem ser equivalententemente definidos como grafos com clique ≤ 2, grafos com cintura ≥ 4, grafos sem caminho induzido com três vértices, ou grafos localmente independentes.

Pelo Teorema de Turán, um grafo sem triângulos de n-vertíces com o número máximo de arestas é um grafo bipartido completo em que o número de vértices em cada lado da bipartição é o mais semelhante possível.

O Problema de encontrar um triângulo é o problema de determinar se um grafo possui ou não um triângulo. Quando o grafo contém um triângulo, normalmente,os algoritmos devem retornar como saída os três vértices que formam um triângulo no grafo.

É possível testar se um grafo de m-arestas não forma um triângulo em tempo O(m^1.41).

Outra abordagem usada é encontrando o traço de A³, onde A é a matriz de adjacência do grafo. O traço é igual a zero se somente se o grafo não forma triângulos. Para grafos densos, usar um algoritmo simples que se baseia na multiplicação de matrizes é mais eficiente, visto que a complexidade de tempo é de O(n^2.373), onde n é o número de vértices.

Como Imrich, Klavžar & Mulder (1999) mostrou, reconhecer um grafo sem triângulo é equivalente a reconhecer um grafo mediano em termos de complexidade; entretanto, o melhor algoritmo atual para o reconhecimento de grafos medianos usa detecção de triângulo em sua subrotina e não vice-versa.

A complexidade da árvore de decisão do problema, onde as consultas são feitas a um oráculo que guarda a matriz de adjacência do grafo, é Θ (n ² ). No entanto, para algoritmos quânticos, o melhor limite inferior conhecido é Ω(n), mas devido à Belovs ( 2011), o algoritmo mais conhecido é O (n ^1,29).

É fácil achar um conjunto independente de √n vertices em um grafo sem triângulo de n-vertíces: Ou há um vértice com mais de √n vizinhos (caso em que os vizinhos são um conjunto independente) ou todos os vértices tem menos de √n vizinhos (caso em que o máximo conjunto independente deve ter no mínimo √n vértices).^[1] Esse limite pode ser reduzido um pouco mais: Para cada grafo sem triângulos, existe um conjunto independente de ${\displaystyle \Omega ({\sqrt {n\log n}})}$ vértices, e em alguns grafos sem triângulos, cada conjunto independente tem ${\displaystyle O({\sqrt {n\log n}})}$ vértices. Uma maneira de generalizar grafos sem triângulos em que todos os conjuntos independentes pequenos é usando o “processo de eliminar triângulos” ^[2] no qual um grafo máximo sem triângulos é formado adicionando repetidamente de forma aleatória arestas que não formam um triângulo. Com uma grande probabilidade, este processo gera um grafo com o número de independência ${\displaystyle O({\sqrt {n\log n}})}$. Com isso também é possível encontrar grafos regulares com as mesmas propriedades.

Esses resultados também podem ser interpretado como limitantes assintóticos no números de ramsey R(3,t) da formúla ${\displaystyle \Theta ({\tfrac {t^{2}}{\log t}})}$: se as arestas de um grafo completo em ${\displaystyle \Omega ({\tfrac {t^{2}}{\log t}})}$ vértices são coloridos em vermelho e azul, então ou o grafo vermelho contém um triângulo ou, se não tiver triângulos, ele deve ter um conjunto independente de tamanho t correspondente ao clique do mesmo tamanho no grafo azul.

Muitas das pesquisas sobre grafos livres de triângulos são concentrados na coloração de grafos. Cada grafo bipartido (ou seja, cada 2-cores) é livre de triângulo, e o teorema de Grötzsch afirma que a cada grafo planar livre de triângulo pode ser 3-cores.^[3] No entanto, os grafos sem triângulo não planos podem exigir muito mais do que três cores.

Mycielski (1955) definiu uma construção, agora chamada de Mycielskian, para a formação de um novo grafo livre de triângulos a partir de outro grafo livre de triângulos. Se um grafo tem número cromático k, seu Mycielskian tem como número cromático k + 1, logo, essa construção pode ser usada para mostrar que um grande número arbitrário de cores podem ser necessário para colorir um grafo livre de triângulos não-planar. Em particular, o grafo de Grötzsch, um grafo de 11 vértices formados a partir da aplicação repetida da construção de Mycielski, é um grafo livre de triângulos que não é possível colorí-lo usando no mínimo 4 cores e é o menor grafo com essa propriedade. Gimbel &Thomassen & (2000) e Nilli (2000) mostraram que o número de cores necessárias para colorir qualquer grafo livre de triângulos de m-arestas é : ${\displaystyle O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)}$

e que existem grafos livre de triângulos que tem números cromáticos proporcionais a esse limite.

Também existem vários resultados relacionados a coloração de grau mínimo em grafos livre de triângulos. Andrásfai, Erdős & Sós (1974) provou que qualquer grafo livre de triângulos de n-vértices em que cada vértice tem mais de 2n/5 vizinhos deve ser bipartido. Isso é o melhor resultado possível desse tipo, como 5-ciclos requer três cores, mas tem exatamente 2n/5 vizinhos por vértice. Motivado por esse resultado, Erdős & Simonovits (1973) conjecturou que qualquer grafo livre de triângulo em que cada vértice tem pelo menos n/3 vizinhos pode ser colorido usando apenas 3 cores; entretanto, Häggkvist (1981) provou o contrário encontrando um contra-exemplo em que cada vértice do grafo de Grötzsch é substituido por um conjunto independente com um tamanho escolhido cuidadosamente. Jin (1995) mostrou que qualquer grafo livre de triângulos em que cada vértice tem mais 10n/29 vizinhos deve ser colorido com 3 cores; isso é o melhor resultado possível para esse tipo, pois o grafo de Häggkvist necessita de 4 cores e tem exatamente 10n/29 viznhos por vértice. Finalmente, Brandt & Thomassé (2006) provou que qualquer grafo livre de triângulos de n-vértices em que cada vértice tem mais de n/3 vizinhos deve ser 4-cores. Outros resultados para este tipo de grafos não é possível, visto que Hajnal^[4] achou exemplos de grafos livre de triângulos com um grande número arbitrário de cores e grau mínimo (1/3 − ε)n para qualquer ε > 0.

Notes

Sources

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