Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose that $\vec{G}$ is a directed graph and that $G$ is the undirected graph obtained from $\vec{G}$ by forgetting the direction on each edge. Define $\vec{H}$ to be a minor of $\vec{G}$ if $H$ is a minor of $G$ as undirected graphs and direction on the edges of $\vec{H}$ are the same as the corresponding edges in $\vec{G}$.

Does the Robertson-Seymour Theorem hold for directed graphs (where the above definition of minor is used and our graphs are allowed to have loops and multiple edges)?

share|cite|improve this question

I think the answer is yes, see 10.5 in Neil Robertson and Paul D. Seymour. Graph minors. xx. wagner’s conjecture. Journal of Combinatorial Theory, 92:325–357, 2004. and the preceding section:

As a corollary, we deduce the following form of Wagner’s conjecture for directed graphs (which immediately implies the standard form of the conjecture for undirected graphs). A directed graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges.

10.5 Let $G_i$ ($i = 1,2,\ldots$) be a countable sequence of directed graphs. Then there exist $j > i \geq 1$ such that $G_i$ is isomorphic to a minor of $G_j$.

I haven't tried to understand the proof and I don't plan to try anytime soon. But I'm pretty sure that the used definition of digraph minor is identical to your definition, and that the statement is exactly the theorem you asked for.

share|cite|improve this answer
The two answers contradict themselves and quote the same author... – Denis Nov 6 '14 at 4:50
@Denis My guess would be that the other answer was the first answer by a new user, and got its votes through the corresponding review queue. In the review queue, you can only see the answer and the question, but not the other answers. The main claim I make in this answer is that the definition "A directed graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges." is equivalent to the definition given in the question. If you want to challenge this claim, or think I should it explain it in more detail, please let me know. – Thomas Klimpel Nov 6 '14 at 8:14

No. Digraphs are not well-quasi ordered under minor containment. However a subclass of digraph, namely semi-complete tournament (a fully connected DAG), are WQO under minor containment. Source: recent (2011-2012) paper by Seymour.

share|cite|improve this answer
In this paper they don't use the minor definition of the question, but what they call "immersion" and it is not the same. – Denis Nov 25 '14 at 16:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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