The reduction of graph families closed under contraction (Q1126283): Difference between revisions

A non-empty family \(\gamma\) of graphs is said to be closed under contraction if for all graphs \(G\) in the family \(\gamma\) and all edges \(e\) of \(G\), the contraction \(G/e\) belongs to \(\gamma\), provided that the definition of contraction \(G/H\) (\(H\) denotes a non-empty subgraph of \(G\)) says that the contraction \(G/H\) is the graph obtained from \(G\) by contracting all edges in \(H\) and by deleting any resulting loops. Introducing the concepts of a complete family, a free family and a kernel of a family, the author establishes a lot of very interesting properties concerning the three concepts. He concludes by developing a reduction method using contractions to find when a given graph belongs to a family \(\gamma\).