Matching covered graphs and subdivisions of \(K_ 4\) and \(\bar C_ 6\) (Q1924125)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Matching covered graphs and subdivisions of \(K_ 4\) and \(\bar C_ 6\) |
scientific article |
Statements
Matching covered graphs and subdivisions of \(K_ 4\) and \(\bar C_ 6\) (English)
0 references
26 January 1997
0 references
A connected graph is matching covered if each of its edges lies in some perfect matching and bicritical if deletion of any two of its vertices yields a graph having a perfect matching. A 3-connected bicritical graph is called a brick. A subgraph \(H\) of a matching covered graph \(G\) is nice if \(G- H\) has a perfect matching. An odd subdivision of a graph \(G\) is a graph obtained from \(G\) by subdividing each edge in an odd number of edges. This paper gives a very simple proof that every non-bipartite matching covered graph contains a nice subgraph that is an odd subdivision of \(K_4\) or \(\overline{C_6}\). It follows immediately that every brick different from \(K_4\) and \(\overline{C_6}\) has an edge whose removal preserves the matching covered graph property. These are classical and very useful results due to Lovász.
0 references
perfect matching
0 references
brick
0 references
matching covered graph
0 references
odd subdivision
0 references