Decomposição otima em orelhas para grafos matching covered

AUTOR(ES)

Marcelo H. Carvalho

DATA DE PUBLICAÇÃO

1996

RESUMO

Matching covered graphs are connected graphs in which every edge lies in a perfect matching. The base of this theory was developed by L. Lovász, and as consequence, a characterization to the matching lattice was obtained. Then it was possible to obtain a proof for a relaxation of a conjecture of Tutte, which is related to the four colors problem. There are two main decomposition procedures of a matching covered graph: tight cuts decomposition and ear decomposition. For ear decomposition one can use single or double ears. One important question asks about the minimum number of double ears of any ear decomposition of such graphs. This work gives an answer to this question It is also presented two consequences: that there is a base for the matching lattice formed solely by incidence vectors of perfect matching, and a characterization to Lin (M, Z2 ) which gives a proof to an other relaxation of the Tutte conjecture

ASSUNTO(S)

teoria dos grafos - processamento de dados teoria dos grafos

Documentos Relacionados

• Modular decomposition of undirected graphs
• Algoritmos para emparelhamentos em grafos bipartidos
• Algoritmos para emparelhamento em grafos e uma implementação paralela
• Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos
• Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos