Examples of Minor-closed Families
The following sets of finite graphs are minor-closed, and therefore (by the Robertson–Seymour theorem) have forbidden minor characterizations:
- forests, linear forests (disjoint unions of path graphs), pseudoforests, and cactus graphs;
- planar graphs, outerplanar graphs, apex graphs (formed by adding a single vertex to a planar graph), toroidal graphs, and the graphs that can be embedded on any fixed two-dimensional manifold;
- graphs that are linklessly embeddable in Euclidean 3-space, and graphs that are knotlessly embeddable in Euclidean 3-space;
- graphs with a feedback vertex set of size bounded by some fixed constant; graphs with Colin de Verdière graph invariant bounded by some fixed constant; graphs with treewidth, pathwidth, or branchwidth bounded by some fixed constant.
Read more about this topic: Robertson–Seymour Theorem
Famous quotes containing the words examples of, examples and/or families:
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)
“Awareness has changed so that every act for children, every piece of legislation recognizes that children are part of families and that it is within families that children grow and thrive—or don’t.”
—Bernice Weissbourd (20th century)