4
$\begingroup$

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"?

  • 0
    Harry, I meant "labeling", thanks. Editing question.2011-04-19

1 Answers 1

4

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).

  • 0
    Still no - see my updated answer.2011-04-19