GRAPH COLORING AND ITS APPLICATIONS

Graph Coloring and Its applications
Project for HERITAGE INSTITUTE OF TECHNOLOGY
1st semester CSE dept.

1. i
i
HERITAGE INSTITUTE OF TECHNOLOGY
DEPT. - COMPUTER SCIENCE AND ENGINEERING
1
ST
YEAR SECTION ‘A’
PROJECT : COLORING OF GRAPHS and ITS APPLICATIONS

GROUP MEMBERS :
•MANOJIT CHAKRABORTY ROLL NO. 1451050
•SAPTARSHI KUNDU ROLL NO. 1451052
•RISHU RAJ ROLL NO. 1451048
•PALLAVI MAZUMDER ROLL NO. 1451053

2.  GRAPH COLORING :
1. Vertex coloring :
It is a way of coloring the vertices of a graph such that no
two adjacent vertices share the same color.

A (vertex) coloring of a graph G is a mapping c : V(G) S.
→
The elements of S are called colors; the vertices of one
color form a color class. If |S| = k, we say that c is a k-
coloring (often we use S = {1, . . . , k}).

Clearly, if H is a sub graph of G then any proper coloring of G
is a proper coloring of H.
Edge and Face coloring can be transformed into Vertex
version

3. 2. Chromatic number :

 χ = least number of colors needed to color a graph.
Chromatic number of a complete graph:
χ(K
n
) = n
The chromatic number χ(G) is the smallest k such that G has proper k-coloring. G is
called k-chromatic.
•Properties of χ(G) :
 
There are a lot of theorems regarding χ(G).But we are not going to prove them.
 
χ(G) = 1 if and only if G is totally disconnected
χ(G) ≥ 3 if and only if G has an odd cycle (equivalently, if G is not bipartite)
χ(G) ≥ ω(G) (clique number)
χ(G) ≤ Δ(G)+1 (maximum degree)

4. 3. Four color theorem :
 Francis Guthrie (1852)
  The four color map theorem, states that, given any separation of a plane into contiguous regions,
producing a figure called a map, no more than four colors are required to color the regions of the map so
that no two adjacent regions have the same color.
 It has many failed proofs.
 4-color theorem finally proved in 1977 (Appel, Haken).First major computer-based proof
Optimal 4 coloring example :

5. A graph is 2-colorable iff it is bipartite
ω(G) – size of largest clique in G
χ(G) ≥ ω(G)
–Clique of size n requires n colors
–χ(G)=7, ω(G) =5.

 Mycielski’s Construction
–It Can be used to make graphs with arbitrarily
large chromatic numbers, that do not contain K
3

as a sub graph.

6. 5. 5 color theorem :

•All planar graphs can be colored with at most 5 colors
•Basis step: True for n(G) ≤ 5
•Induction step: n(g) > 5
•There exists a vertex v in G of degree at most 5.
•G – v must be 5-colorable by induction hypothesis

Proof by example :
•If G is 5-colorable, done
•If G is not 5 colorable, we have:
•Is there a Kempe chain including v1 and v3?

7. There is no Kempe chain There is a Kempe chain
There cannot be a Kempe chain v4 cannot directly influence v2 including v2 and v4

8. 6. Edge coloring :

An edge-coloring of G is a mapping f : E(G)→S. The element of S
are colors; the edges of one color form a color class. If |S| = k, then f
is a k-edge-coloring.
•Every edge-coloring problem can be
transformed into a vertex-coloring problem
•Coloring the edges of graph G is the same as
coloring the vertices in L(G)
•Not every vertex-coloring problem can be
transformed into an edge-coloring problem
•Every graph has a line graph, but not every
graph is a line graph of some other graph

9. 7. Applications of Graph Coloring:
The graph coloring problem has huge number of applications.

•Making Schedule or Time Table:
•Mobile Radio Frequency Assignment:
•Sudoku: 
•Register Allocation:
•Bipartite Graphs: 
•Map Coloring: 

10. Each cell is a vertex
Each integer label is a “color”
A vertex is adjacent to
another vertex if one of the
following hold:
Same row
Same column
Same 3x3 grid
Vertex-coloring solves Sudoku
Applications: Sudoku

11.  Applications – coloring graphs

•Color a map such that two regions with a common border are assigned different
colors.•Each map can be represented by a graph:
–Each region of the map is represented by a vertex;
–Edges connect two vertices if the regions represented by these vertices have a
common border.
•The resulting graph is called the dual graph of the map.

12. Application – GSM Networks :
The Groupe Spécial Mobile (GSM) was created in 1982 to provide a standard for a mobile
telephone system. The first GSM network was launched in 1991 by Radiolinja in Finland
with joint technical infrastructure maintenance from Ericsson. Today, GSM is the most
popular standard for mobile phones in the world, used by over 2 billion people across more
than 212 countries. GSM is a cellular network with its entire geographical range divided
into hexagonal cells. Each cell has a communication tower which connects with mobile
phones within the cell. All mobile phones connect to the GSM network by searching for
cells in the immediate vicinity. GSM networks operate in only four different frequency
ranges. The reason why only four different frequencies suffice is clear: the map of the
cellular regions can be properly colored by using only four different colors! So, the vertex
coloring algorithm may be used for assigning at most four different frequencies for any
GSM mobile phone network

13.  THANK YOU