◀ ▲ ▶Branches / Graph-theory / 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 BY-SA 4.0! 
- Github:
-
References
Bibliography
- Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000
