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

  • 1
    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.2011-04-19
  • 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
    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)?2011-04-19
  • 0
    Still no - see my updated answer.2011-04-19