An extension of matching theory (Q1057288): Difference between revisions

Given a graph G and a family of hypermatchable subgraphs of G, we introduce the notion of a hypomatching of G relative to H as a collection of node disjoint edges and subgraphs, where the subgraphs all belong to H. Examples include matchings \((H=\emptyset)\), fractional matchings (H contains all the hypomatchable subgraphs of G) and edge-and-triangle packings (H is the set of 3-cliques of G). We show that many of the classical theorems about maximum cardinality matchings can be extended to hypomatchings which cover the maximum number of nodes in a graph.