Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Does the Robertson-Seymour theorem apply to vertex-labeled graphs? A minor as I understand it is a graph which can be reached by a sequence of edge contractions and non-disconnecting edge deletions. It seems natural to define a label-minor in the same way, but with the restriction that an edge can be contracted only if it connects vertices of the same label. Is every label-minor-closed set of vertex-labeled graphs characterized by a finite set of minimal forbidden label-minors?

Sorry if this is a naive question as I have only recently been studying this topic, mostly on Wikipedia. Any introductory references would be appreciated. Is there a standard term for what I am calling "label-minor"?

share|cite|improve this question
Is there any specific kind of coloring are you talking about? Normally a "coloring" of a graph is one where adjacent vertices have different colors, so the only thing you could do is remove edges. – Harry Stern Apr 19 '11 at 4:33
Harry, I meant "labeling", thanks. Editing question. – Dan Brumleve Apr 19 '11 at 5:35
up vote 4 down vote accepted

No. One of the ways to interpret the R-S theorem is that in any infinite set of finite graphs, one is a minor of another. This clearly isn't the case under your definition of labeled minors; just take any sequence of finite graphs that don't have any minors at all since all the vertices have distinct labels.

EDIT: the answer is still No even if only 2 labels are available. Just consider infinitely many even cycles of different sizes, each one 2-colored in the natural way; none of these is a minor of another (indeed, none of these has any proper minors at all).

share|cite|improve this answer
This convinces me that the answer is no in the general case of an infinite number of labels. But certainly the answer is yes if there is only one label as this is the R-S theorem itself. What is the answer if up to some other number of labels are permitted (e.g. 2)? – Dan Brumleve Apr 19 '11 at 6:00
Still no - see my updated answer. – Alon Amit Apr 19 '11 at 6:42

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.