Graph Coloring Problem

Introduction to Graph Coloring Problem

Graph coloring refers to the problem of coloring vertices of a graph in such a way that no two adjacent vertices have the same color. This is also called the vertex coloring problem.

  • If coloring is done using at most k colors, it is called k-coloring.
  • The smallest number of colors required for coloring graph is called its chromatic number.
  • The chromatic number is denoted by X(G). Finding the chromatic number for the graph is NP-complete problem.
  • Graph coloring problem is both, decision problem as well as an optimization problem. A decision problem is stated as, “With given M colors and graph G, whether such color scheme is possible or not?”.
  • The optimization problem is stated as, “Given M colors and graph G, find the minimum number of colors required for graph coloring.”
  • Graph coloring problem is a very interesting problem of graph theory and it has many diverse applications. Few of them are listed below.

Applications of Graph Coloring Problem

  • Design a timetable.
  • Sudoku
  • Register allocation in the compiler
  • Map coloring
  • Mobile radio frequency assignment:

The input to the graph is an adjacency matrix representation of the graph. Value M(i, j) = 1 in the matrix represents there exists an edge between vertex i and j. A graph and its adjacency matrix representation are shown in Figure (a)

Graph Coloring Problem
(a). Graph G
  C1 C2 C3 C4 C5
C1 0 1 0 1 0
C2 1 0 1 0 0
C3 0 1 0 1 1
C4 1 0 1 0 1
C5 0 0 1 0 0
Adjacency matrix for graph G

The problem can be solved simply by assigning a unique color to each vertex, but this solution is not optimal. It may be possible to color the graph with colors less than |V|. Figure (b) and figure (c) demonstrate both such instances. Let Ci denote the ith color.

(b). Nonoptimal solution (uses 5 colors)
Example of Graph Coloring Problem
(c). Optimal solution (uses 2 colors)
  • This problem can be solved using backtracking algorithms as follows:
    • List down all the vertices and colors in two lists
    • Assign color 1 to vertex 1
    • If vertex 2 is not adjacent to vertex 1 then assign the same color, otherwise assign color 2.
    • Repeat the process until all vertices are colored.
  • Algorithm backtracks whenever color i is not possible to assign to any vertex k and it selects next color i + 1 and test is repeated. Consider the graph shown in
    Figure (d)
Graph Coloring using backtracking
Figure (d)

If we assign color 1 to vertex A, the same color cannot be assigned to vertex B or C. In the next step, B is assigned some different colors 2. Vertex A is already colored and vertex D is a neighbor of B, so D cannot be assigned color 2. The process goes on. State-space tree is shown in Figure (e)

Figure (e): State-space tree of the graph of Figure (d)

Thus, vertices A and C will be colored with color 1, and vertices B and D will be colored with color 2.

Algorithm

Algorithm for graph coloring is described here :

Algorithm

 GRAPH_COLORING(G, COLOR, i)
// Description :  Solve the graph coloring problem using backtracking
// Input : Graph G with n vertices, list of colors, initial 
vertex i
// COLOR[1…n] is the array of n different colors

// Output : Colored graph with minimum color

if

 CHECK_VERTEX(i) == 1 

then


  

if

i == N 

then


    

print

COLOR[1…n]
  

else


    j ← 1
    

while

(j ≤ M) 

do


      COLOR(i + 1) ← j     
      j ← j + 1
    

end


  

end


end



Function

CHECK_VERTEX(i)

for

j ← 1 to i – 1 

do


  

if

Adjacent(i, j) 

then


    

if

COLOR(i) == COLOR(j) 

then


       

return

0
    

end


  

end


end

					

return

1

Complexity Analysis 

The number of anode increases exponentially at every level in state space tree. With M colors and n vertices, total number of nodes in state space tree would be
1 + M + M2 + M3 + …. + Mn

Hence, T(n) = 1 + M + M2 + M3 + …. + Mn

= frac{M^{n+1} - 1}{M - 1}

So, T(n) = O(Mn).

Thus, the graph coloring algorithm runs in exponential time.

Planar Graphs

  • A graph is called planar if it can be drawn on a 2D plane such that no two edges cross each other. The graph coloring problem is a well-known problem of a planar graph.
  • Planar and non-planar graphs are illustrated in Fig. (f) & Fig. (g)
Planar graph
Fig. (f): Planar graph
Graph Coloring Problem
Fig. (g): Non-Planar graph

Bipartite graph 

  • Graph G is said to be a bipartite graph if we can divide the vertices of graph G into two disjoint sets, U and V such that each edge connects a vertex in U to one vertex in V. Disjoint independent sets, U and V are called partite sets. If we cut the edges with vertical lines, all vertices become isolated vertices. Fig. (h) describes the bipartite graph.
  • It is intuitive from the figure that we need a maximum of two colors for graph coloring problem if the graph is bipartite. None of the vertexes in U and V is connected to any other vertex in the set itself.
Fig. (h): Bipartite Graph

All vertices in U can be colored using one color as there is no adjacency between vertices. Similarly, vertices in V can be colored using one color. Thus, a bipartite graph needs only two colors for graph coloring problems.

Examples on Graph Coloring Problem

Example: Apply backtrack on the following instance of graph coloring problem of 4 nodes and 3 colors

Solution:

This problem can be solved using backtracking algorithms. The formal idea is to list down all the vertices and colors in two lists. Assign color 1 to vertex 1. If vertex 2 is not adjacent to vertex 1 then assign the same color, otherwise assign color 2. The process is repeated until all vertices are colored. The algorithm backtracks whenever color i is not possible to assign to any vertex k and it selects the next color i + 1 and the test is repeated. This graph can be colored with 3 colors. The solution tree is shown in Fig. (i):

FIg. (i): Solution tree
Vertex Assigned Color
1 c1
2 c2
3 c3
4 c1

Example: Construct a planar graph for the following map. Explain how to find m-coloring of this planar graph by using an m-coloring Backtracking algorithm

Fig. J

Solution:

In Fig. (j), area 1 is adjacent to areas 2, 3, and 4. So, in a planar graph, vertex 1 will be connected to vertices 2, 3, and 4.

Area 2 is adjacent to areas 1, 3, 4, and 5, so in a planar graph, vertex 2 will be connected to vertices 1, 3, 4, and 5. This process will be repeated for all areas. Hence, the planar graph would be,

  • This problem can be solved using backtracking algorithms as follows:
    • List down all the vertices and colors in two lists
    • Assign color 1 to vertex 1
    • If vertex 2 is not adjacent to vertex 1 then assign the same color, otherwise assign color 2.
    • Repeat the process until all vertices are colored.

The algorithm backtracks whenever color i is not possible to assign to any vertex k and it selects the next color i + 1 and the test is repeated. This graph can be colored using four different colors. A gray node indicates backtracking.

Backtracking is useful in solving the following problems:


Additional Reading: Read More

You may also like...

Leave a Reply

Your email address will not be published.