9
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I am especially interested in question 1... No understandable proof scheme of Robertson-Seymour theorem exists ? $\endgroup$
    – Denis
    Commented Nov 28, 2014 at 14:52

2 Answers 2

Reset to default
8
$\begingroup$

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/

Improve this answer
$\endgroup$
7
$\begingroup$

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. 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 by A. Atminas, V. Lozin, and I. Razgon.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – Hermann Gruber
    Commented Jan 6, 2015 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.