Graph coloring

Mohammed Brahimi
Module distribution concerns raised by students
• Issues
• Multiple difficult modules scheduled in the same term
• Unbalanced distribution of workload between terms

• Goal
• Achieving a balanced load distribution between terms

• Approach:
• Represent modules as vertices
• High-load modules are linked by edges
• Assign colors to terms
• Ensure that difficult and high-load modules are not scheduled in the same term.

Find optimal module-term assignment to minimize load imbalance

and avoid clustering high-load modules.
How to avoid challenging modules in the same term?
How to avoid challenging modules in the same term?

1 8

3 5 4

6 2
How to avoid challenging modules in the same term?

1 8

3 5 4

6 2
How to avoid challenging modules in the same term?

Term 1
1 6 8 2

3 7 5 4

Term 2
How to avoid challenging modules in the same term?

• Term 1 Term 1
• Data structure
• Linear Algebra 2 1 6 8 2
• Databases
• Analysis 3

• Term 2
• Architecture 1 7 5 4
3
• Mathematical Logic
• Complexity Term 2
• Probability and Statistics
Problem extension

• What if a teacher teach two modules together:

• Assign a unique color to each teacher.
• Modules taught by the same teacher are adjacent vertices in the graph.
• Find a suitable coloring for the graph representing the modules and teachers.

• What about other time table constraints:

• Sessions represented as vertices.
• Make two vertices adjacent based on any constraints.
• Ensure that conflicting sessions, are not scheduled in parallel.

Create a well-structured time table that considers teacher availability,

room constraints, and avoids conflicts between modules.
What is graph coloring ?
• In the context of a simple graph G, a k-coloring refers to the assignment of
at most k colors to its vertices.
• k-coloring should color the adjacent vertices in G by different colors.
• If G has a valid k-coloring, we say G is k-colorable.
• The chromatic number of G, denoted by 𝜒(𝐺), is the smallest number k for
which G is k-colorable.

• Reason for restricting coloring to simple graphs:

• Vertex with loop cannot be assigned a different color from itself.
• The presence of one or multiple edges between two vertices has a similar effect,
requiring them to be colored differently.
What is the chromatic number 𝜒(𝐺) ?

a) 𝜒(𝐺) = 1 a) 𝜒(𝐺) = 3
• One color is sufficient • + 3 colors are required (presence of triangle)
• Absence of edges • It exists 3-coloring.
b) 𝜒(𝐺) = 2 b) 𝜒(𝐺) = 4
• +1 color is required (presence of edges) • +4 colors are required (presence of 𝑘4 )
• It exists 2-coloring. • It exists 4-coloring.
Subgraphs and the Chromatic Number
• Subgraphs play a crucial role in understanding the chromatic number of a
graph.

• If a subgraph 𝐻 of 𝐺 has a chromatic number 𝜒(H), then 𝜒(G) must also be

at least that value.

• The presence of complete subgraphs (cliques) can increase the chromatic

number of a graph.

The subgraphs with the highest chromatic numbers can provide insights
into the chromatic number of the entire graph.
THEORME 1 (coloring bipartite graph)
A graph is bipartite if and only if it is 𝜒(𝐺)=2

• Direction 1: Bipartite graph ⟹ Chromatic number is 2.

• In a bipartite graph, vertices can be split into two sets, A and B, where all edges connect
vertices from different sets.
• Assign color 1 to set A
• Assign color 2 to set B.
• This yields a valid 2-coloring.
• Thus, the chromatic number of a bipartite graph is 2.

• Direction 2: Chromatic number is 2 ⟹ Graph is bipartite.

• If a graph can be colored with only two colors:
• Put all the vertices of color 1 to the set A
• Put all the vertices of color 2 to the set B
• Two vertices from A (or B) are not adjacent because they have the same color.
• This results in a partition of the graph into sets A and B where the vertices of each set are not
adjacent.
What is the chromatic number ?

• Complete graph 𝐾𝑛 • Cycle graph 𝐶𝑛 (n>2)

• All the vertices are connected • 𝜒(𝐺)=2, if n =2k
• 𝜒(𝐺)=n • 𝜒(𝐺)=3, if n =2k+1

• Path graph 𝑃𝑛 (n>1) • Wheel graph 𝑊𝑛 (n>1)

• Alternate the colors • 𝜒(𝐺) = 4, if n =2k
• 𝜒(𝐺)=2 • 𝜒(𝐺) = 3, if n =2k+1
THEORME 2
let G be a simple graph whose maximum vertex degree is d. Then
𝜒 𝐺 ≤𝒅+𝟏

• Intuition
• If the maximum vertex degree of a graph is low, we can determine a tight
upper bound for the chromatic number.
• However, for graphs with a high maximum degree, this theorem becomes less
effective or loses its usefulness.
Proof
• Proof by induction on the number of vertices 𝑛

• The statement is true for 𝐾1 the simple graph with one vertex
• 𝜒 𝐾1 = 1 and 𝑑 = 𝑂.

• We assume that 𝜒 𝐺 ≤ 𝑑 + 1 for all simple graphs 𝐻 with fewer than or equal 𝑛
vertices.

• We should show that 𝜒 𝐺 ≤ 𝑑 + 1 for all simple graphs 𝐺 with 𝑛 + 1 vertices.

Proof
• Let 𝐺 be a simple graph with 𝑛 + 1 vertices and maximum vertex
degree 𝑑.

• Let 𝐻 be a graph obtained from 𝐺 by removing a vertex 𝑣 and its

incident edges.

• 𝐻 has at most 𝑛 vertices and a maximum vertex degree of 𝑑 or less. By

our assumption, we have 𝜒(𝐻) ≤ 𝑑 + 1.

• By assigning an unassigned color to 𝒗, we can create a (𝑑+1)-coloring

of 𝐺. Therefore, 𝝌(𝑮) ≤ 𝒅 + 𝟏.

• In the worst-case scenario, if deg(𝒗) = 𝒅 and all vertices have unique

colors, exactly one unassigned color remains.
THEOREM 3 (Brooks 1941)
Let 𝐺 be a connected simple graph whose maximum vertex degree is d.
lf 𝐺 is neither a cycle graph with an odd number of vertices, nor a
complete graph, then :
𝜒(𝐺) ≤ 𝑑.

• Intuition
• The theorem does not works for 𝐾𝑛 and 𝐶2𝑘+1
• This theorem provides a stricter upper limit for the chromatic number.
Chromatic Number 𝜒(𝐺) and Bounds
• To determine the chromatic number 𝜒(𝐺) of a graph 𝐺, find an equal upper and
lower bound, which becomes the chromatic number 𝜒(𝐺).

• Possible upper bounds for 𝜒(𝐺)

• Total number of vertices in 𝐺.
• Number of colors in an explicit vertex coloring of 𝐺.
• Maximum degree (d) in G plus one (Theorem 2).
• Maximum degree (d) in G, if G is not an odd cycle or complete graph 𝐾𝑛 (Brooks' theorem).

• Possible lower bound for 𝜒(𝐺)

• Number of vertices in the largest complete subgraph in G.
Coloring Planar Graphs
• THEOREM 4 (Six Colors Theorem for Planar Graphs)
The vertices of any simple connected planar graph 𝐺 can be coloured
with six (or fewer) colours.

• Intuition:
• For planar graphs, it is possible to color them using 6 colors or fewer.
• Even highly complex planar graphs can be colored using a maximum of 6
colors.
Proof
• Proof by induction on the number of vertices 𝑛

• The statement is trivially true when 𝑛 = 1

• Assuming simple connected planar graphs with fewer or equal than 𝑛

vertices can be colored with 6 or fewer colors

• We aim to prove the same for simple connected planar graphs with
𝑛 + 1 vertices.
Proof
• Let 𝐺 be a simple graph with 𝑛+1 vertices

• 𝐺 contains a vertex 𝑣 of degree 5 or less (Previous lecture).

• Create graph 𝐻 by removing vertex 𝑣 and its incident edges from 𝐺.

• By our assumption, the vertices of 𝐻 can be colored with 6 colors.

• Reintroduce vertex 𝑣.
• An unassigned color is available because 𝑣 has a degree ≤ 5 and there are 6
available colors.
• We color 𝑣 with this unsaigned color.

• This results in a 6-coloring of the vertices in 𝐺.

THEORME 5 (Five Colors Theorem for Planar Graphs)

The vertices of any simple connected planar graph G can be colored

with five (or fewer) colors.

• Intuition:
• For planar graphs, it is possible to color them using only 5 colors or fewer.
• Even highly complex planar graphs can be colored using a maximum of 5
colors.
Proof
• Proof by induction on the number of vertices 𝑛

• The statement is trivially true when 𝑛 = 1

• Assuming simple connected planar graphs with fewer or equal than 𝑛

vertices can be colored with 5 or fewer colors

• We aim to prove the same for simple connected planar graphs with
𝑛 + 1 vertices.
Proof
• Let 𝐺 be a simple graph with 𝑛+1 vertices

• 𝐺 contains a vertex 𝑣 of degree 5 or less (Previous lecture).

• Create graph 𝐻 by removing vertex 𝑣 and its incident edges

from 𝐺.

• By our assumption, the vertices of 𝐻 can be colored with 5

colors.

• If we reintroduce vertex 𝑣, three cases appear

• Case 1: If there is an unassigned color, we are done
• Case 2: two colors are not linked path
• Case 3: two colors are connected with a path
Case 2: two colors are not linked path

By switching one color to be the same as another color, we created an unassigned color.
Case 3: two colors are connected with a path

We simply switch two colors without creating an unassigned color.

 Case 3: two colors are connected with a path

The planarity prevents the colors from forming a path due to existing path
Another proof of case 3
• The graph is contracted by removing two edges,
resulting in a planar graph with fewer than 𝑛
vertices.

• The contracted graph is 5-colorable.

• The two edges are reinstated, assigning the

original color of 𝑣 to both 𝑣1 and 𝑣3 .

• Assign to 𝑣 a an unassigned color in the

contracted grpah

• A 5-coloring of the graph G is achieved by

coloring.
THEORME 6 (Four Colour Theorem for Planar Graphs )

The vertices of any simple connected planar graph can be colored with four (or
fewer) colours.

Intuition
• It states that only 4 colors are needed to color the regions oof any map.
• Conjectured in the 19th century.
• Proven in 1976 with computer assistance.
• It demonstrates the inherent simplicity within complex spatial configurations.
Greedy Algorithm for Vertex Colouring
• Start with graph G and a list of colors 1, 2, 3, ...

• Step 1:
• Label the vertices as a, b, c, ... in any manner.

• Step 2:
• Identify the uncolored vertex labeled with the earliest letter in the alphabet.
• Color this vertex with the first color from the list that is not used by any adjacent colored vertex.
• Repeat Step 2 until all vertices are colored.

• Stop. A vertex coloring of G has been obtained.

• The number of colors used depends on the labeling chosen for the vertices in Step 1.
Example
Find a vertex colouring of the following
graph G.
• Step 1:
• Label the vertices as a, b, c, ... in any
manner.
• Step 2:
• Identify the uncolored vertex labeled with
the earliest letter in the alphabet.
• Color this vertex with the first color from
the list that is not used by any adjacent
colored vertex.
Example
Find a vertex colouring of the following
graph G.
• Step 1:
• Label the vertices as a, b, c, ... in any
manner.
• Step 2:
• Identify the uncolored vertex labeled with
the earliest letter in the alphabet.
• Color this vertex with the first color from
the list that is not used by any adjacent
colored vertex.
THEORME 6
For any graph G, there is a labelling of the vertices for which the greedy
algorithm yields a vertex colouring with 𝜒(𝐺) colours.

• Proof sketch
• Take any vertex coloring of G with 𝜒(𝐺) colors, denoted by 1, 2, 3, ...
• Sequentially label the vertices colored 1 as a, b, c, ...
• Label the vertices colored 2 starting from the next available label after the last label
used for color 1.
• Continue this labeling pattern for the vertices colored 3, 4, and so on.
• The greedy algorithm assigns colors 1, 2, 3, ... in order.
• As a result, only 𝜒(𝐺) colors are needed for this labeling.
Coloring Problems: Storing Chemicals
• Certain chemicals react violently when they are
in contact.

• The manufacturer plans to divide the

warehouse into regions to separate dangerous
chemical pairs.

• The dangerous pairs of chemicals are marked

with an asterisk in a table.

The objective is to find the minimum number of

areas required to safely store the chemicals.
Coloring Problems
• To determine the minimum number of areas required for safe chemical
storage, a graph was created.
• Each vertex represent chemical.
• Vertices are adjacent when the corresponding chemicals need to be separated.

Assigning chemicals to areas is a vertex coloring problem, with colors

corresponding to the areas.

• A vertex coloring leads to a vertex decomposition of the graph, where no

adjacent vertices are in the same subset.

• The subsets {a, e}, {b, j}, {c}, {d, g}, representing the chemicals in the four
areas.

• The minimum number of subsets required for this problem is the

chromatic number 𝜒(𝐺) of this graph.
Coloring Problems: Map Colouring
• In 1852, Francis Guthrie proposed the four-color problem:
• Can all maps be colored with four colors so that neighboring countries have different
colors?

• Mathematicians, including De Morgan, Cayley, and Kempe, studied the

problem.

• In 1976, Appel and Haken provided a proof using nearly 2000 country
configurations and extensive computer analysis.

Even today, no "simple" proof has been discovered for the four-color
problem.
Coloring Problems: Map Colouring
• Objective:
• Assign colors to countries on a map,
ensuring adjacent countries have different
colors.
• Representation:
• Use the geometrical dual to represent
countries as vertices in a graph, with
edges connecting adjacent countries.

Determine the minimum number of colors

needed to avoid adjacent countries sharing
the same color.
Coloring Problems: Map Colouring
A map is planar graph

• Theorem 4: Any map can be colored with 6 colors .

• Theorem 5: Any map can be colored with 5 colors .

• Theorem 6: Any map can be colored with 4 colors .

Coloring Problems: Register allocation
• Register allocation can be seen as a graph
coloring problem.
• Nodes in the graph represent the live ranges of
variables.
• Edges indicate connections between two live
ranges.
• The objective is to assign colors to nodes such
that adjacent nodes have different colors.

The chromatic number represents the minimum

number of registers required.
Let's play Sudoku
• Objective:
• Complete a 9x9 matrix.

• Criteria:
• In each row, column, and
marked 3x3 square, the
numbers 1 to 9 should occur
exactly once.

Can we model this as coloring

problem ?!
Conclusion
• Graph coloring is a fundamental concept in graph theory with diverse applications.

• It enables the assignment of colors to vertices by representing entities as vertices and their
relationships as edges.

• The goal is to ensure adjacent vertices have different colors, minimizing conflicts.

• Efficient graph coloring algorithms are crucial for optimizing resource allocation and improving
system performance.

• Understanding graph coloring techniques helps solve complex optimization problems in various
domains.

• Graph coloring has applications beyond computer science, contributing to advancements in

diverse fields.
Reference