Graph coloring is a type of graph homomorphism.
Let be graph. The graph is -colorable if it is possible to assign for each vertex colors such that adjacent vertices have different colors.
A graph is -edge colorable if its edges can be colored with colors so that no two adjacent edges (i.e., edges that share an endpoint) have the same color .
A map is -face colorable if its faces can be colored with colors such that no two faces with a boundary edge in common have the same color.

Chromatic Number

The chromatic number of denoted implies that is -colorable but not -colorable.
A graph has a chromatic index denoted if it is -edge colorable but not edge colorable.
(Godsil 1.4.1) The chromatic number of a graph is the least integer such that there is a homomorphism from to .
- Proof: In the forward case, if the homomorphism exists, then a partition based on which elements map to in the image will form independent sets which correspond to the color classes. Conversely, if such a coloring exists, then the homomorphism maps to .
(Wilson Ch. 18) Brook’s Theorem - If is a simple connected graph and not an odd cycle, and if , then is -colorable.
Vizing’s Theorem ¹

Four Color Theorem

Let be a simple graph. The chromatic polynomial, denoted is the number of ways to perform a vertex coloring with colors available.
- If
(Aydelotte 2.6, Wilson 21.2). The chromatic polynomial is a polynomial.
The Deletion-Contraction Formula. If is a simple ² graph, then
(Aydelotte 2.4) Let be a simple graph, be a decomposition of . Then
(Aydelotte 3.1) The degree of l is the number of vertices of .
(Aydelotte 3.2) The chromatic polynomial has the following properties.
1. The Leading Coefficient of is .
2. The absolute value of the coefficient of the term in is the number of edges of .
3. The first coefficient of is positive, and all terms alternate in sign.
4. All coefficients are integer.
5. If the coefficient of , then so is .
(Aydelotte 3.2) The constant term of the chromatic polynomial of any graph is .
(Aydelotte 3.7) The chromatic polynomial of is
(Aydelotte 3.8) The chromatic polynomial of
(Theorem) The chromatic polynomial of a tree of vertices is
Read’s Theorem For a given chromatic polynomial with coefficients , is unimodal. That is, there is some such that

Two undirected graphs are said to be chromatically equivalent if they have the same chromatic polynomial but they are not isomorphic.
An undirected graph is chromatically unique if for any graph with the same chromatic polynomial as , then
An undirected graph is a -critical if and the vertex deletion of any vertex yields a graph with a smaller chromatic number, namely for vertex we have
(Wilson e17.11.3a) Let be -critical. Then
- Proof: Argue by contradiction. If , then has at most neighbors, and the induced subgraph is colorable. The Pigeonhole Principle applies and we find that we can replace the color of and we have the original graph as colorable.
(Wilson e17.11.3b) Let be a -critical graph. Then does not contain cut vertices. A special case of Wilson e17.11.3b.
- Proof: Let consist of components by virtue of being a cut-vertex. Now, is colorable. Any component combined with (and the edges to ) is colorable. Taking the union of the components gives us a coloring.
(Wilson e17.11z) Let be a -critical graph. Any vertex cut of cannot be in a clique.
- This follows from Wilson e17.11.3b except applying the argument to multiple vertices instead.