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

A (proper) vertex coloring of a graph is a labelling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color. A coloring using at most $k$ colors is called a (proper) $k$-coloring.

The $k$-coloring partitions the vertex set of a graph into $k$ sets. What do I say to refer to one of these sets of vertices? For example, "fix a vertex coloring of $G$ and let $A$ be the (blank) of largest order."

Is there a standard terminology? Also, if there are multiple terms, what other words for these might I see floating around?

share|cite|improve this question
up vote 3 down vote accepted

The most common term for the collection of vertices receiving the color $i$ is "the $i^\text{th}$ color class" (or just "color class" if you do not wish to specify its color).

share|cite|improve this answer

I would talk about (maximal) monochromatic components.

share|cite|improve this answer
Not that I am a reference or something, but I saw it in a couple articles. – beauby Nov 25 '12 at 0:13
In my experience, "component" is generally reserved for "connected component" in graph theory. – Austin Mohr Nov 25 '12 at 0:17
Indeed; a monochromatic component is a connected component of the subgraph induced by the vertices with a given colour (in an improper colouring); see e.g. [this](‌​. – Douglas S. Stones Jan 6 '13 at 0:16

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.