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:
“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)
“In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
—Michel de Montaigne (1533–1592)
“The brotherhood of men does not imply their equality. Families have their fools and their men of genius, their black sheep and their saints, their worldly successes and their worldly failures. A man should treat his brothers lovingly and with justice, according to the deserts of each. But the deserts of every brother are not the same.”
—Aldous Huxley (1894–1963)