Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

https://en.wikipedia.org/wiki/Graph_minor

minor type

Topological minors

https://zhuanlan.zhihu.com/p/351950187

image-20230704111814863

A graph H is called a topological minor of a graph G if a subdivision of H is isomorphic to a subgraph of G

另一种:https://www.graphclasses.org/classes/gc_309.html

G is a minor of H if G can be obtained from H be a series of vertex deletions, edge deletions and/or edge contractions (replacing two adjacent vertices u,v by a vertex that is adjacent to all neighbours of u or v).

Minor-closed graph families

Many families of graphs have the property that every minor of a graph in F is also in F; such a class is said to be minor-closed.

https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem

example:

the planar graphs are closed under taking minors: contracting an edge in a planar graph, or removing edges or vertices from the graph, cannot destroy its planarity

the collection of all planar graphs and, more generally, all graphs that can be embedded in a fixed surface

Topological-Minor-Free Graph Classes

A graph G is K4*-minor-free if* K4 isn’t a minor of G.

评论