Decomposição de um grafo em caminhos: aspectos estruturais e algorítmicos

Resumo

Investigaremos neste projeto um problema clássico da teoria dos grafos sobre partição do conjunto das arestas de um grafo em um número mínimo de caminhos. Este problema tem suas raízes numa conjectura de Gallai (1966) sobre uma cota superior para esse número, que só depende do número de vértices do grafo. Esta conjectura afirma que o conjunto das arestas de um grafo conexo com n vértices pode ser decomposto em no máximo (n+1)/2 caminhos. A literatura a respeito desta conjectura é relativamente pequena: sabe-se que ela foi estabelecida para o caso em que o grafo só tem vértices de grau ímpar e para o caso em que os vértices de grau par induzem um subgrafo com uma estrutura bem especial. Temos interesse em investigar a validade dessa conjectura para outras classes de grafos e também explorar aspectos algorítmicos deste problema. Resultados algorítmicos sobre este problema não foram encontrados na literatura.