Partição em caminhos e conjuntos independentes em digrafos

Resumo

Este projeto tem como tema a relação entre partições em caminhos e conjuntos independentes em digrafos. Dizemos que uma partição dos vértices em caminhos direcionados em um digrafo e um conjunto independente são \emph{ortogonais} se cada caminho da partição tem precisamente um vértice do conjunto independente. Em 1960, Gallai e Milgram demonstraram que uma partição em caminhos com o menor número possível de caminhos em um digrafo sempre é ortogonal a algum conjunto independente do digrafo. Sendo assim, o menor número de caminhos necessários para cobrir todos os vértices em uma partição em caminhos, denotado por $\pi$, é um limite inferior para o tamanho do maior conjunto independente do digrafo, denotado por $\alpha$. Posteriormente, em 1982, Berge propôs uma conjectura que estende a observação de Gallai e Milgram para uma noção mais generalizada de minimalidade em partições em caminhos e $k$-colorações em digrafos. Dado um $k$ inteiro e positivo, Berge propôs uma nova métrica de minimalidade de uma partição em caminhos em função de $k$, e buscou com sua conjectura relacioná-la ao maior número de vértices que podem ser coloridos com $k$ cores de forma que cada conjunto independente seja ortogonal à partição em caminhos. O Teorema de Gallai e Milgram é um caso particular da Conjectura de Berge, no qual $k=1$. O objetivo desta iniciação científica é estudar essa antiga conjectura de Berge e entender os resultados parciais conhecidos até o momento, aprofundando este estudo no caso $k=1$, o mais importante resolvido. Para $k=1$ existe algoritmo polinomial conhecido, derivado do Teorema de Gallai e Milgram, para encontrar a partição em caminhos ótima e um conjunto independente ortogonal à mesma. (AU)