## Tuesday, August 14, 2007

### Graph minor and some results

Theorem: (Wagner's conjecture)
For every class of graphs $\cal{G}$, that is closed under taking of minors, there exists a finite set of graphs, ob($\cal{G}$), called the obstruction set of $\cal{G}$, such that for each graph G, $G\in \cal{G}$ if and only if there is no $H\in ob(\cal{G})$ that is a minor of $\cal{G}.$

Theorem:
For every graph H, there exists an $O(n^3)$ time algorithm, that, given a graph G, tests whether H is a minor of G.

Theorem:
For every planar graph H, there exists a constant c(H), such that for every graph G, if H is not a minor of G, then the treewidth of G is at most c(H).

BarrosH said...

Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring.
by Demaine ED, Hajiaghayi MT, Kawarabayashi KI

Joseph, Chuang-Chieh Lin said...

Thanks, BarrosH.

Joseph, Chuang-Chieh Lin said...

（自己回應）