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

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

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