<p>For question (2): the subgraph and induced subgraph relations give rise to well quasi orders on some restricted classes of graphs.  One of the main references there is an article by G. Ding, <em>Subgraphs and well-quasi-ordering</em>, J. Graph Theory, 16: 489–502, 1992, <a href="http://dx.doi.org/10.1002/jgt.3190160509">doi:10.1002/jgt.3190160509</a>.  The paper </p>

<ol>
<li>shows that both orderings yield wqos on the class of graphs with bounded path lengths, and</li>
<li>even more interestingly, characterises exactly the hereditary classes of graphs for which the subgraph ordering becomes a wqo (the class should contain only finitely many cycles and "H-graphs").</li>
</ol>

<p>More results in the case of the induced subgraph ordering can be found in this <a href="http://arxiv.org/abs/1410.3260">recent arXiv paper</a> by A. Atminas, V. Lozin, and I. Razgon.</p>

CC BY-SA 3.0
2015-01-06T21:27:23.963Z
The following paper might be of interest as well in this regard: M.R. Fellows, D. Hermelin, F.A. Rosamond: Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs and their Algorithmic Applications. Algorithmica 64(1):3-18, 2012
Hermann Gruber
CC BY-SA 3.0
2014-11-27T16:44:40.510Z
2014-11-27T16:44:40.510Z
Sylvain
<p>The following book covers some material related to the proof of the graph minor theorem (Chapter 12). </p>

<p>Reinhard Diestel: Graph Theory, 4th edition, Graduate Texts in Mathematics 173.</p>

<p>The author states: "[...] we have to be modest: of the actual proof of the minor theorem, this chapter will convey only a very rough impression. However, as with most truly fundamental results, the proof has sparked off the development of methods of quite independent interest and potential." </p>

<p>An electronic version of the book can be viewed online. 
<a href="http://diestel-graph-theory.com/">http://diestel-graph-theory.com/</a></p>

CC BY-SA 3.0
2014-12-02T20:04:10.287Z
2014-12-02T20:04:10.287Z
Hermann Gruber
<p>This question is two-fold, and is mainly reference-oriented:</p>

<ol>
<li><p>Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know the proof is long and difficult, but surely there must be key ideas that can be communicated in an easier way.</p></li>
<li><p>Are there other relations on graphs that can be shown to be well quasi-orders, maybe in a simpler way than for the minor relation? (obviously I am not interested in trivial results here, like comparing sizes). Directed graphs are also in the scope of the question.</p></li>
</ol>

CC BY-SA 3.0
2014-11-28T14:52:12.440Z
I am especially interested in question 1... No understandable proof scheme of Robertson-Seymour theorem exists ?
Denis
<reference-request><graph-theory><graph-minor>
Understanding graph minor theorem
Denis
# Understanding graph minor theorem

(Asked by: username_0 on 2014-11-27)

This question is two-fold, and is mainly reference-oriented:

1. Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know the proof is long and difficult, but surely there must be key ideas that can be communicated in an easier way.
2. Are there other relations on graphs that can be shown to be well quasi-orders, maybe in a simpler way than for the minor relation? (obviously I am not interested in trivial results here, like comparing sizes). Directed graphs are also in the scope of the question.

**Tags:** reference-request, graph-theory, graph-minor

> **Comments:**
> **username_0**: I am especially interested in question 1... No understandable proof scheme of Robertson-Seymour theorem exists ?  

---

## 2 answers

### Answer by username_2 on 2014-12-02. Score: 8 | Accepted answer

The following book covers some material related to the proof of the graph minor theorem (Chapter 12).

Reinhard Diestel: Graph Theory, 4th edition, Graduate Texts in Mathematics 173.

The author states: "[...] we have to be modest: of the actual proof of the minor theorem, this chapter will convey only a very rough impression. However, as with most truly fundamental results, the proof has sparked off the development of methods of quite independent interest and potential."

An electronic version of the book can be viewed online.
<http://diestel-graph-theory.com/>


---

### Answer by username_1 on 2014-11-27. Score: 7

For question (2): the subgraph and induced subgraph relations give rise to well quasi orders on some restricted classes of graphs. One of the main references there is an article by G. Ding, *Subgraphs and well-quasi-ordering*, J. Graph Theory, 16: 489–502, 1992, [doi:10.1002/jgt.3190160509](http://dx.doi.org/10.1002/jgt.3190160509). The paper

1. shows that both orderings yield wqos on the class of graphs with bounded path lengths, and
2. even more interestingly, characterises exactly the hereditary classes of graphs for which the subgraph ordering becomes a wqo (the class should contain only finitely many cycles and "H-graphs").

More results in the case of the induced subgraph ordering can be found in this [recent arXiv paper](http://arxiv.org/abs/1410.3260) by A. Atminas, V. Lozin, and I. Razgon.

> **Comments:**
> **username_2**: The following paper might be of interest as well in this regard: M.R. Fellows, D. Hermelin, F.A. Rosamond: Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs and their Algorithmic Applications. Algorithmica 64(1):3-18, 2012  

---

