Graph Theory Course
Chapter VI: Graph Coloring
Dr. B. Sidaoui
Sepember 2024
Abstract
This chapter focuses on the graph coloring problem, covering vertex coloring,
edge coloring, and face coloring. It also discusses the Four color theorem and the
Welsh-Powell algorithm.
1
Chapter VI: Graph coloring
1 Introduction
A graph coloring is an assignment of labels, called colors, to the vertices of a graph such
that no two adjacent vertices share the same color.
The minimal number of colors for which such an assignment is possible, is called the
chromatic number γ(G). Other types of coloring on graphs also exist, most notably edge
coloring.
2 Definition
Let G = (V, E) be a graph. A proper coloring of G using k colors is defined as a function
ϕ, such that:
(∀ v, u ∈ V, ∀(v, u) ∈ E) → (ϕ(v) ̸= ϕ(u)) (1)
The set of proper colorings of G using k colors is denoted by Ck (G).
3 Chromatic number
The minimum number of colors required to properly color a graph G = (V, E) is called the
chromatic number, denoted by γ(G). The chromatic number has the following properties:
• Let d(G ′ ) represent the order of the largest clique in a graph G, then γ(G) ≥ d(G ′ ).
• Let d(G) denote the maximum degree of the vertices in G, then γ(G) ≤ d(G) + 1.
• The chromatic number γ(G) is within the interval: d(G ′ ) ≤ γ(G) ≤ d(G) + 1.
Let G be a graph with a largest clique of order 4 and a maximum degree of 5. Therefore,
the chromatic number satisfies 4 ≤ γ(G) ≤ 6.
4 Types of graph coloring
The most common types of graph coloring include:
1. Vertex coloring: Assigning colors to vertices such that no two adjacent vertices
have the same color.
2. Edge coloring: Assigning colors to edges such that no two edges sharing a com-
mon vertex have the same color. A set of edges without common vertices forms a
matching partition.
3. Face coloring: Used primarily in planar graphs, where regions (faces) are colored
such that adjacent regions do not share the same color.
SALHI Ahmed University Center of Naâma 2
Chapter VI: Graph coloring
5 Matching concept
A matching in a graph is a set of edges where no two edges have a vertex in common. In
other words, a matching pairs vertices such that each vertex is part of at most one pair.
Matching Example : For a bipartite graph with vertices U = {u1, u2, u3} and V =
{v1, v2, v3}, a maximum matching could be (u1, v2), (u2, v3), and (u3, v1)
6 Four color theorem
Any planar graph can be colored with at most four colors such that no two adjacent
vertices share the same color.
7 Welsh Powell algorithm
The Welsh-Powell algorithm is used to find a solution to the graph coloring problem by
determining the minimum number of colors needed for vertex, edge, or face coloring,
ensuring that no two adjacent vertices share the same color. The Welsh-Powell algorithm
is given by the following steps:
1. Sort the vertices (nodes) in descending order of their degrees.
2. Assign the first color to the vertex with the highest degree and color all other vertices
that are not adjacent to it with the same color.
3. Move to the next uncolored vertex (highest degree) and repeat the process, assigning
a new color to that vertex and other uncolored, non-adjacent vertices.
4. Repeat this process until all vertices are colored.
8 Exercise
Determine the optimal coloring for the undirected graph (nodes, edges, and faces) shown
in the following figure, ensuring that adjacent vertices do not share the same color.
SALHI Ahmed University Center of Naâma 3
Chapter VI: Graph coloring
Figure 1: A undirected graph
SALHI Ahmed University Center of Naâma 4