3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.