Next: Bonin Abstract Up: Index of Abstracts Previous: Abstracts of talks

Lovasz Abstract

The matching structure of graphs

A graph is called matching-covered, if every edge of it belongs to a perfect matching; bicritical, if deleting any two nodes, the rest has a perfect matching; and it is a brick, if it is 3-connected and bicritical.

A decomposition theory going back to the work of Kotzig in the 50's shows that every graph with a perfect matching can be decomposed (in a well-described, "canonical" way) into matching-covered graphs; these in turn can be decomposed in bicritical graphs; these in turn can be decomposed into brick. With help of this decomposition, many theorems on perfect matchings in graphs can be reduced to the case of bricks.

The finer structure of bricks is less well understood. Lovasz proved that (with the exception of the complete 4-graph and the complement of the 6-cycle), every brick contains an edge whose deletion leaves it matching-covered.

Recently Lov\'asz and S. Vempala proved the stronger result that every brick (with the exception of the two graphs above and the Petersen graph) contains an edge whose deletion, followed by a further, rather simple reduction, leaves a smaller brick. This leads to a recursive generation of all bricks, and also to the simplification of various proofs.