Decomposições de grafos

Resumo

Um grafo G é um par (V,E), onde V é um conjunto finito e E é um conjunto de pares de elementos distintos de V. Os elementos de V são chamados vértices, e os elementos de E são chamados arestas. Dado um grafo G = (V,E), uma decomposição de G é um conjunto de subgrafos aresta-disjuntos de G que cobrem E. Se D = {H_1,...,H_k} é uma decomposição de G tal que H_i é um caminho para todo i em {1,...,k}, dizemos que D é uma decomposição por caminhos.Dizemos que uma decomposição por caminhos de um grafo G é mínima se para toda decomposição por caminhos D' de G, temos que |D'|>=|D|. O path number de um grafo G é o tamanho de uma decomposição por caminhos mínima. Denotamos o path number de G por pn(G). De acordo com Lovász (1968), em 1966, Erdös perguntou sobre este parâmetro, e Gallai estabeleceu a seguinte conjectura. Conjectura (Gallai, 1966). Se G = (V,E) é um grafo conexo com n vértices, então pn(G) <= (n+1)/2.Esse parâmetro não é conhecido para a maioria das classes de grafos. Lovász (1968) encontrou um limitante superior para um parâmetro similar, o tamanho de uma decomposição mínima em caminhos e circuitos.Teorema (Lovász, 1968). Todo grafo conexo com n vértices pode ser decomposto em no máximo n/2 caminhos e circuitos.Nosso plano é investigar a conjectura de Gallai, o path number de classes especiais de grafos, e tópicos relacionados. Sabemos que essa conjectura é verdadeira para várias classes de grafos, mas isso ainda não foi determinado para classes de grafos como grafos com grau máximo 4, grafos 2k-regulares, grafos cordais, ou grafos planares.Nós também estamos interessados no aspecto algorítmico do problema de encontrar uma decomposição por caminhos mínima de um grafo. Não foram encontrados resultados relacionados a este tópico, diferentemente do caso em que se busca caminhos disjuntos nos vértices. Deste ponto de vista estamos interessados em algoritmos de aproximação.O estudo desse tema justifica-se pela sua releância: um problema clássico, de grande interesse na área de grafos. Em se tratando de uma conjectura que está aberta há quase meio século, seria muita pretensão ter como objetivo estabelecer de vez a sua validade ou não. Temos porém a certeza de que um estudo dessa natureza irá dar ao aluno a oportunidade de aprender técnicas de provas e entender onde reside a dificuldade do problema. (AU)