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.

Problema de encontrar um triângulo

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

Número de Independência e Teoria de Ramsey

É 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). Esse limite pode ser reduzido um pouco mais: Para cada grafo sem triângulos, existe um conjunto independente de $\Omega ({\sqrt {n\log n}})$ vértices, e em alguns grafos sem triângulos, cada conjunto independente tem $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” 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 $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 $\Theta ({\tfrac {t^{2}}{\log t}})$: se as arestas de um grafo completo em $\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.

Coloração de grafos livres de triângulos

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. 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 é : $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 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.

Referências

Notes

Sources

Ligações externas

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