Graph Colorings

In this lesson we look at ways of coloring things in a graph (where 'things' means vertices, edges or faces) in such a way that adjacent things are colored differently.

Vertex Colorings

The vertices must be colored differently if they are joined by an edge.

Edge Colorings

Edges with vertces in common must be colored differently.

Face Colorings

Faces with adjacent edges are always colored differently.

Note We are usually interested in knowing the smallest number of colors that have to be used to color a graph.

Vertex Colorings

Definition A graph is said to be k-vertex colorable (or just k-colorable) if its vertices can be colored using up to k different colors in such a way that each vertex is of a single color and any two adjacent vertices have different colors (i.e. so that no two vertices of the same color are adjacent).

Definition The vertex chromatic number, or simply the chromatic number of a fintite, loop-free graph G is the smallest positive number k such that G is k-colorable. The chromatic number of a graph G is usually denoted by c (G).

Note The graph must be loop-free, because if vertices are allowed to have loops, then they can be adjacent to themselves. If a vertex is adjacent to itself, then it must be colored a different color from itself, which is impossible.

Examples The triangle graph has chromatic number 3.

The cube graph has chromatic number 2.

Lemma For a finite, loop-free graph, G, c(G) = 2 if and only if G is a bipartite graph.

Proof Firstly, suppose that G is a bipartite graph, with parts A and B, then color all vertices in A red, and all vertices in B blue. Then every edge joins a blue vertex to a red vertex. Therefore, G is 2-colorable, so c(G)=<2. Now, (G) > 1, since once you have an edge, you need at least two colors.

Next, assume that c(G) = 2. Consider any vertex coloring of G with colors red and blue. Then, by the definition of a vertex coloring, every edge joins a red vertex to a blue vertex. Therefore, G is bipartite with red vertices in one part, and blue vertices in the other part. This completes the proof of the lemma.

Note c(K_n) = n. Since any two vertices are joined by an edge and must therefore be colored differently.

Theorem If every vertex of G has degree d(v) < k, then G is k-colorable.

Proof Use induction on n, the number of vertices of the graph G. If n = 1 or n = 2, the assertion is easily seen to be true. Suppose n > 2, and assume that the proposition is valid for all graphs with fewer than n vertices.

Choose any vertex v of G and delete it and all the edges incident to v. This leaves a subgraph H of G with n - 1 vertices satisfying the given hypothesis (i.e. that every vertex has degree less than k). By the inductive hypothesis, c(H) k, i.e. H is k-colorable.

Now, consider any particular k-coloring of H. Since d(v) < k, the vertices of H that were adjacent to v in G are colored with at most k-1 different colors. Thus, there's at least one color left with which we may color v, so that it is of a different color to each of its neighbors. This gives a coloring of G using the same colors as H. Therefore, G is k-colorable. This completes the proof of the theorem.

Note The bound,

cannot be improved. For example, K_n. However, the theorem can be improved to Brook's theorem.

Theorem (Brook's Theorem).

If , then G is k-colorable, unless it has a connected component isomorphic to K_{k + 1} (i.e. the complete graph on k + 1 vertices.)

Remark Brook's Theorem shows that the complete graphs are the 'worst cases' for vertex colorability.

Examples The Peterson graph can be represented pictorially as,

The Peterson graph has maximum vertex degree 3, and does not have a connected component isomorphic to K₄. Therefore, c (Peterson) = 3.

Dual Graphs and Face Colorings

If G has m edges, n verteices and f faces, then the dual G⁸ has f vertices, m edges and n faces.

Note that (G^*)^* is isomorphic to G.

Theorem (The Six Color Theorem for Finite Planar Graphs).

If G is a finite, simple planar graph, then G is 6-colorable (i.e. c(G)=<6).

Proof If G has fewer than seven vertices, then the result is obvious. Suppose that G has n vertices with n>=7. For induction, suppose that all such graphs on n-1 vertices are 6-colorable. Now, planarity and Euler's Polyhedron Formula implied that G has at least one vertex with degree less than 6, say vertex v. Remove this vertex and all edges incident to it, leaving a subgraph H on n-1 vertices, which is 6-colorable (by the inductive hypothesis). Then v can be colored with any color different to the colors of its (fewer than 6) neighbors. This completes the proof of the Six Color Theorem.

Note This theorem can be improved to the 'Five Color Theorem,' and ultimately to the 'Four Color Theorem.'

Face Colorings

Definition A map is a simple, connected plane graph with no isthmus (i.e. an edge whose removal disconnects the graph into two components).

Definition A map is said to be k-colorable if all of its faces can be colored with k colors (each face of one color) so that no two faces with a common edge have the same color.

Note A map is k-colorable (faces) if and only if the vertices of the dual graph are k-colorable.

Edge Colorings

Definition A graph G is said to be k-edge colorable if its edges can be colored using up to k-colors such that no two edges with a vertex in common have the same color.

Example

Definition The smallest positive integer k for which G is k-colorable is called the edge- chromatic number of G, and it is denoted by c_e(G).

Theorem (Vizings Theorem).

If G is a finite, loop-free graph whose largest vertex degree is r, then:

r=<c_e(G)=<r + 1.