Bases for the Matching Lattice of Matching Covered Graphs

Resenhas IME-USP 1995, Vol. 2, No. 2, 219-227.

Bases for the Matching Lattice of Matching Covered Graphs

Cláudio L. Lucchesi and Marcelo H. Carvalho

Department of Computer Science
University of Campinas
13081-970 Campinas, SP
Brazil
E-mail addresses: lucchesi@dcc.unicamp.br and mhc@dcc.unicamp.br

Abstract

This article contains a brief introduction to the theory of matching covered graphs: ear-decompositions, the matching lattice and the most important results of the theory. In its last section we prove that the matching lattice of any matching covered graph has a basis consisting solely of perfect matchings and we present a conjecture relating the minimum number of double ears of any ear-decomposition of a matching covered graph and the number of bricks and bricks isomorphic to the Petersen graph in any brick decomposition of the same graph.

Back to Table of Contents

Last modified: Sun Oct 29 18:51:00 GMT 1995