Discover published sets by community

Explore tens of thousands of sets crafted by our community.

Categories

Mathematics

Graph Theory

Graph Minor Theorems

Flashcards

0/5

Still learning

Minor of a Graph

A graph H is a minor of a graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

Wagner's Theorem

A graph is planar if and only if it does not have a $K_5$ (complete graph on 5 vertices) or $K_{3,3}$ (complete bipartite graph on two sets of 3 vertices) as a minor.

Graph Minor Theorem (Robertson-Seymour Theorem)

Every family of graphs closed under taking minors is characterized by a finite set of forbidden minors.

Treewidth and Graph Minors

If a graph G has a tree decomposition of width at most $k$ , then any minor of G also has a tree decomposition of width at most $k$ .

Excluded Grid Minor Theorem

For every integer $n$ there is an integer $f(n)$ such that every graph of treewidth at least $f(n)$ contains the $n \times n$ grid as a minor.

Know

Still learning

Click to flip

Know