Proper graph coloring

A proper vertex coloring of a graph $G=(V,E)$ by a color set $C$ is a function $c:V\to C$ satisfying

\{u,v\}\in E\ \Longrightarrow\ c(u)\ne c(v).

A proper $k$ -coloring uses $C=\{1,\ldots,k\}$ . Some available colors may be unused.

Interpretation

Each color class contains no adjacent pair. If adjacency represents two supports that can interact, one color can be reused at vertices whose supports cannot interact. A coloring only encodes the adjacency rule used to construct the graph; it does not establish that the rule captures all relevant interactions.

References

Tait, Introduction to Combinatorics, Proposition 3.1.10 (greedy coloring).