Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/101406
Type: Artigo de periódico
Title: On A Conjecture Of Lovász Concerning Bricks. I. The Characteristic Of A Matching Covered Graph
Author: De Carvalho M.H.
Lucchesi C.L.
Murty U.S.R.
Abstract: In 1987, Lovász conjectured that every brick G different from K4, C̄6, and the Petersen graph has an edge e such that G-e is a matching covered graph with exactly one brick. Lovász and Vempala announced a proof of this conjecture in 1994. Their paper is under preparation. In this paper and its sequel (M. H. de Carvalho, C. L. Lucchesi, and U. S. R. Murty, 2002, J. Combin. Theory Ser. B 85, 137-180) we present a proof of this conjecture. We shall in fact prove that if G is a brick different from K4,C̄6, R8 that does not have the Petersen graph as its underlying simple graph, then it has two edges e and f such that both G-e and G-f are matching covered graphs with exactly one brick, with the additional property that, in each case, the underlying simple graph of that one brick is different from the Petersen graph. A cut C of a matching covered graph G is a separating cut if the two C-contractions of G are matching covered. In this paper, we introduce the notion of the characteristic of a separating cut in a matching covered graph and establish some basic properties. We use those properties to first prove our theorem for solid bricks, that is, bricks which do not have any nontrivial separating cuts. The proof of the theorem for nonsolid bricks will be presented in the sequel. © 2002 Elsevier Science (USA).
Editor: 
Rights: fechado
Identifier DOI: 10.1006/jctb.2001.2091
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-0036263917&partnerID=40&md5=492132887f6e94fc432bbac0f54ecc37
Date Issue: 2002
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-0036263917.pdf282.4 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.