# What are the sets of vertices in a proper vertex coloring referred to?

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?

-

## 2 Answers

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

-

I would talk about (maximal) monochromatic components.

-
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](www.csse.monash.edu.au/~gfarr/research/small-monochromatic-components.ps)‌​. –  Douglas S. Stones Jan 6 '13 at 0:16