Welcome to MathOverflow

Question

4

For definitions of graph minors and topological minors, see wikipedia's article on graph minors.

Theorem: For every graph H, there is a finite set of graphs, say S(H), such that G contains H as a minor if and only if G contains some graph from S(H) as a topological minor.

Can anyone point me to a paper/book where this is proved? (I know how to prove it, I just want a reference to cite.)

flag	asked Aug 30 2010 at 4:28 Robin Kothari 918●4●11

Nathann Cohen · Accepted Answer · 2010-08-30 06:32:20Z UTC

4

Hello !!! You will find this theorem as results 2.2 and 2.3 in Graph minors VIII : A Kuratowski theorem for general surfaces.

Nathann

answered Aug 30 2010 at 6:32

Nathann Cohen
731●3●8

2

The paper Nathann refers to is online at dx.doi.org/10.1016/0095-8956(90)90121-F – András Salamon Aug 30 2010 at 8:12

Perfect. That's exactly what I needed. – Robin Kothari Aug 30 2010 at 15:31

Ref request: A graph G contains H as a minor iff it contains one of finitely many graphs as a topological minor

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.