Decomposição otima em orelhas para grafos matching covered

TL;DRAbstract

O assunto do qual se trata este trabalho se insere na area de teoria dos grafos, e mais especificamente de grafos matching covered, que sao grafos conexos em que toda aresta pertence a um emparelhamento perfeito. L. Lovasz desenvolveu toda a base da teoria dos grafos matching covered e, como consequencia, obteve uma caracterizacao para o matching lattice. Desta caracterizacao foi possivel obter uma prova para uma relaxacao da conjectura de Tutte que generaliza o problema das quatro cores. Existem dois procedimentos de decomposicao de grafos matching covered que sao fundamentais: um deles e a decomposicao em cortes justos e o outro e a decomposicao em orelhas. Para uma decomposicao em orelhas podem ser usadas orelhas simples ou duplas. Uma importante questao e determinar o numero minimo de orelhas duplas de uma decomposicao em orelhas de um grafo matching covered. Neste trabalho apresentamos uma resposta para esta questao. Apresentamos tambem duas consequencias desta solucao: uma delas

Chat with Paper

AI Agents for this Paper