6
$\begingroup$

The Robertson-Seymour theorem (aka graph minor theorem) states that any minor-closed class of graphs has a finite number of forbidden minors. I am interested in the case where the class is given by the "minor closure" of a graph, i.e. the collection of all minors of a graph. I imagine it wouldn't be too hard to find some explicit description of the forbidden minors for this class, but I'm not sure. I can imagine a couple: the empty graph on |V(G)|+1 vertices and adding an edge between non-adjacent vertices. I'm not sure if this is all of them.

Is anyone familiar with this problem?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The forbidden minors $\mathcal{F}$ are empty graph on $V(G)+1$ vertices and all graphs have at most $V(G)$ vertices and are not minor graphs of $G$. We easily have $\mathcal{F}$ is finite, the empty graph forbids all graphs with more than $V(G)$ vertices, the rest forbid all graphs have at most $V(G)$ vertices and are not minor graphs of $G$, and all graphs which are the minors of $G$ don't take any graph in $\mathcal{F}$ as minor graph.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is this a minimal description of the forbidden minors? $\endgroup$
    – Andrea B.
    Commented Oct 18, 2022 at 11:04
  • 1
    $\begingroup$ We create a poset of all graphs in $\mathcal{F}$ except the empty graph, $F<F'$ if $F$ is minor of $F'$. We take the empty graph and all atom of that poset. To prove this is minimal, we just need to prove every forbidden minors have a big graph (more than $V(G)$ vertices) and have those atom. $\endgroup$
    – Veronica Phan
    Commented Oct 18, 2022 at 11:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .