◀ ▲ ▶Branches / Graphtheory / Definition: Chromatic Number and `$k$`Coloring of a Graph
Definition: Chromatic Number and $k$Coloring of a Graph
Let $G(V,E)$ be a simple graph and let $K:\{1,\ldots,n\}$ be a set of $n$ "colors". A $k$coloring is a function $f:V\to K$ assigning to the vertices $V$ exactly $k\in K$ colors in such a way that adjacent vertices are assigned different colors. We call $G$ $k$colorable, if it has a $k$coloring.
The chromatic number $\chi(G)$ is the smallest number $k$ for which $G$ is $k$colorable.
Notes
 This definition makes sense for simple graphs only. In general undirected graphs, there might be loops and therefore, a vertex would be adjacent to itself and excluded from coloring.
 Also, multiple edges between two edges are irrelevant for coloring, since even only one edge between two vertices forces the vertices to have different colors.
Mentioned in:
Chapters: 1
Proofs: 2 3 4
Propositions: 5
Theorems: 6 7 8 9 10
Thank you to the contributors under CC BYSA 4.0!
 Github:

References
Bibliography
 Aldous Joan M., Wilson Robin J.: "Graphs and Applications  An Introductory Approach", Springer, 2000