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

    Identifiers