26
$\begingroup$

The theorem of Robertson-Seymour about graph minors says that there exists no infinite family of graphs such that none of them is a minor of another one.

Apparently, it came as a generalization of the Kruskal's theorem that states that there exists no infinite family of rooted ordered trees such that none is a minor of another one. Here, rooted ordered means that the tree has a root, and that the edges escaping from a vertex are ordered. In other words, the trees are assumed to be embedded in the plane, and the minor operation has to respect this embedding.

Here comes the question: is Robertson-Seymour theorem true for planar graphs, when we add the condition that the minor operation respects the embedding? (i.e. we not only ask $G_i$ to be a minor of $G_j$ as an abstract graph, but also as an embedded graph.)

It is not clear to me that this should be a direct corollary of the original theorem, because of the amount of possible embeddings into the plane for a given planar graph.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ @Pierre Dehornoy: I thought that the conclusion of Robertson-Seymour theorem could be strengthened to "A certain graph $G_m$ occurs as a minor infinitely many times in a given infinite sequence" ($G_m$ would be one of the finitely many minimal elements of the sequence, with respect to the "minor" order). If my understanding is correct, then the answer to your question is positive since $G_m$ has only finitely many planar embeddings, up to isotopy, so one of them would be repeated (infinitely often). $\endgroup$
    – Misha
    Commented Mar 28, 2012 at 16:16
  • $\begingroup$ I guess, my understanding of R-S theorem is correct: If a sequence of graphs were to contain infinitely many minimal elements $G_m$ then the new sequence of graphs $(G_m)$ would violate R-S theorem. $\endgroup$
    – Misha
    Commented Mar 28, 2012 at 16:33
  • 2
    $\begingroup$ @ Misha: This looks almost convincing, but I do not understand the end of the argument. One of the embedding of $G_m$ appears infinitely offen, but how does it says that this particular embedding is the one that was given at the beginning, i.e. that corresponds to the given embedding of $G_m$? $\endgroup$
    – Pierre Dehornoy
    Commented Mar 28, 2012 at 23:46
  • $\begingroup$ @Pierre Dehornoy: Pierre, sorry, you a right, this argument does not answer your question. $\endgroup$
    – Misha
    Commented Mar 29, 2012 at 13:05
  • 2
    $\begingroup$ @PierreDehornoy: I think it would improve the question if "true for planar graphs" was replaced with 'true for plane graphs', because what you write immediately afterwards suggests that you are thinking about planar graphs together with a specified embedding into the plane, and that is called a plane graph. $\endgroup$
    – Peter Heinig
    Commented Feb 21, 2018 at 11:46

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .