Decomposição Ótima em Orelhas para Grafos Matching Covered

Marcelo H. de Carvalho (UFMS) Cláudio L. Lucchesi (UNICAMP)

Grafos matching covered são grafos conexos em que toda aresta pertence a um emparelhamento perfeito. O estudo desta classe de grafos é motivado pelo fato de que todo grafo cúbico sem aresta de corte é matching covered. Assim, o estudo desta classe de grafos pode nos dar alguma luz para a solução da Conjectura de Tutte que generaliza o problema das quatro cores.

Existem dois procedimentos de decomposição de grafos matching covered: a decomposição em cortes justos e a decomposição em orelhas. Para uma decomposição em orelhas podem ser usadas orelhas simples ou duplas. Uma decomposição em orelhas é ótima se usa o número mínimo de orelhas duplas. Nesta palestra apresentaremos os principais resultados sobre decomposição ótima em orelhas para grafos matching covered.