# Does the Robertson-Seymour theorem apply to vertex-labeled graphs?

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

-
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