Mais recentemente, na teoria dos grafos têm surgido teoremas que são versões rainbow de alguns teoremas clássicos bem conhecidos. Por exemplo, o Teorema de Dirac (de 1952) afirma que todo grafo de ordem n > 2 cujo grau mínimo é pelo menos n/2 tem um ciclo hamiltoniano. Em 2020, Joos e Kim [Bull. London Math. Soc.] provaram a seguinte versão rainbow do Teorema de Dirac: dada uma coleção G = {G_1, G_2, ..., G_n} de n grafos não necessariamente distintos, todos eles sobre um mesmo conjunto V de n vértices, tal que cada G_i tem grau mínimo pelo menos n/2, então existe uma G-transversal que é um ciclo hamiltoniano sobre V. Ou seja, existe uma bijeção f entre as n arestas de tal ciclo e {1, 2, ...,n} tal que para cada aresta E desse ciclo temos que E pertence a E(G_{f(E)}.

Se considerarmos que cada grafo G_i tem todas suas arestas coloridas com uma mesma cor i, e que a coleção G usa n cores distintas, então uma G-transversal que é um ciclo hamiltoniano tem arestas com cores de 1 a n (em alguma ordem), o que justifica a denominação rainbow. A prova apresentada por Joos e Kim não é algorítmica. Temos interesse em analisar a possibilidade de projetar um algoritmo baseado nessa prova teórica; e se isto for possível, implementar tal algoritmo. Temos interesse em estudar versões rainbow de outros teoremas clássicos, e quando possível, implementar algoritmos baseados nessas provas teóricas.

Por ora, os resultados desse tipo não são muitos, mas estes despertam grande interesse de pesquisadores da área de grafos. Esperamos que este projeto contribua para um bom aprendizado teórico de resultados e técnicas de prova, além de ajudar no desenvolvimento de algoritmos extraídos de provas teóricas.

https://github.com/wmrmrx/TCC