PROFILPELAJAR.COM

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).^[1] 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” ^[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 $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.^[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 é : $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.

Referências

Notes

↑ Boppana & Halldórsson ( 1992). pág. 184, com base na ideia de um algoritmo de coloração aproximado de Avi Wigderson.
↑ Erdős, Suen & Winkler (1995); Bohman (2008)
↑ Grötzsch ( 1959); Thomassen ( 1994).)
↑ see Erdős & Simonovits (1973).

Sources

Alon, N.; Ben-Shimon, S.; Krivelevich, M. (2008). «A note on regular Ramsey graphs». arXiv:0812.2386 .
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, 8 (3): 205–218, doi:10.1016/0012-365X(74)90133-2 .
Bohman, T. (2008). «The triangle-free process». arXiv:0806.4375 .
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 Erdős-Simonovits problem (PDF), consultado em 9 de agosto de 2014, arquivado do original (PDF) em 4 de fevereiro de 2012 .
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}}$ » 3 ed. , Random Structures and Algorithms, 7: 173–207, doi:10.1002/rsa.3240070302 .
Magniez, Frederic; Santha, Miklos; Szegedy, Mario (2003). «Quantum Algorithms for the Triangle Problem». arXiv:quant-ph/0310134 .
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». arXiv:1105.4024 .