Lesson 2

A proper vertex \(k\)-coloring of an undirected graph \(G(V,E)\) is a function \(c \colon V \to [k]\) such that for every edge \(\{u,v\} \in E\) it holds that \(c(u) \neq c(v)\) (in other words, each edge must not be monochromatic). The chromatic number \(\chi(G)\) of a graph \(G\) is the minimum number of colors needed for a proper coloring of its vertices.

As in our formal definition, colors are often represented by numbers when visualizing a graph.