FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Graph Coloring



Introduction

Graph Coloring, also known as the M-Coloring Problem, is a classical application of the Backtracking technique. The objective is to assign colours to all vertices of a graph such that no two adjacent vertices have the same colour while using at most M colours.

Whenever an invalid colour assignment is encountered, the algorithm removes the colour and tries another one. This process continues until a valid colouring is obtained or all possibilities have been explored.

Problem Statement

Given a graph with N vertices and M colours, determine whether the graph can be coloured such that no two adjacent vertices share the same colour.

Why Backtracking?

If assigning a colour to a vertex creates a conflict with an adjacent vertex, the algorithm immediately removes that colour and tries another one. This process of undoing an invalid choice is called Backtracking.

Rules of Graph Coloring

Rule Description
Adjacent Vertices Adjacent vertices cannot have the same colour.
Available Colours Only the given M colours can be used.
Valid Assignment Every vertex must receive exactly one colour.
Conflict Checking Every colour assignment must satisfy graph constraints.

Graph Illustration


          A
         / \
        /   \
       B-----C
       |
       |
       D

Possible Colouring

A → Red

B → Blue

C → Green

D → Red

Figure 1 : One Valid Graph Coloring

Real-Life Example

Suppose neighbouring countries are to be coloured on a map. Two countries sharing a common boundary should not have the same colour. The objective is to colour the entire map using the minimum number of colours. This is a practical application of the Graph Coloring Problem.

Solved Example

Consider the graph shown above and assume that only 3 colours are available:

  • Red
  • Blue
  • Green
Vertex Assigned Colour Status
A Red Valid
B Blue Valid
C Green Valid
D Red Valid

Since no adjacent vertices share the same colour, the colouring is valid.

State Space Tree


          Vertex A

      /      |      \

    Red    Blue    Green

      |

   Vertex B

   /    |    \

 Invalid  Blue  Green

              |

          Vertex C

              |

        Continue...

Figure 2 : State Space Tree for Graph Coloring

Graph Coloring Algorithm

GraphColoring(Vertex) Step 1 : If all vertices are coloured, Display the solution and return. Step 2 : Try every available colour for the current vertex. Step 3 : Check whether the colour is safe. Step 4 : If safe, Assign the colour. Step 5 : Recursively colour the next vertex. Step 6 : If colouring fails, Remove the assigned colour (Backtrack). Step 7 : Try the next available colour.

Dry Run

Consider the graph having four vertices A, B, C and D with three available colours: Red, Blue and Green.

Step Vertex Colour Selected Status
1 A Red Safe
2 B Blue Safe
3 C Red Rejected (Adjacent to A)
4 C Green Safe
5 D Red Safe (Solution Found)

Complexity Analysis

Parameter Complexity Remarks
Best Case O(V) Valid colours are found immediately.
Average Case Depends upon the graph structure. Pruning reduces unnecessary exploration.
Worst Case O(MV) M = Number of colours, V = Number of vertices.
Space Complexity O(V) Recursive call stack and colour array.

Advantages of Graph Coloring

  • Produces a valid colouring whenever one exists.
  • Uses pruning to reduce unnecessary computations.
  • Suitable for constraint satisfaction problems.
  • Simple recursive implementation using Backtracking.
  • Applicable to many scheduling and optimization problems.

Limitations of Graph Coloring

  • Worst-case execution time is exponential.
  • Performance depends on the number of colours and graph structure.
  • Not suitable for very large graphs without optimization.
  • Requires recursive function calls.

Applications of Graph Coloring

Application Description
Map Coloring Assign colours to neighbouring countries without conflicts.
Exam Timetabling Schedule examinations without clashes.
Register Allocation Allocate CPU registers efficiently in compilers.
Frequency Assignment Assign radio frequencies without interference.
Network Scheduling Avoid communication conflicts in computer networks.

Graph Coloring vs N-Queen Problem

Graph Coloring N-Queen Problem
Colours graph vertices. Places queens on a chessboard.
Constraint: Adjacent vertices must have different colours. Constraint: Queens cannot attack each other.
Uses graph representation. Uses chessboard representation.
Solved using Backtracking. Solved using Backtracking.
Used in scheduling and networking. Used in constraint satisfaction and search problems.

💡 Remember This

Adjacent Vertices
↓ Must Have
Different Colours

Always verify neighbouring vertices before assigning a colour.

Important Points

  • Graph Coloring is also called the M-Coloring Problem.
  • It is a classical Backtracking application.
  • Adjacent vertices cannot have the same colour.
  • The algorithm uses a State Space Tree for searching.
  • Invalid colour assignments are removed using Backtracking.
  • Worst-case time complexity is O(MV).

💼 Interview Corner

  • What is the Graph Coloring Problem?
  • Why is Graph Coloring solved using Backtracking?
  • What is the difference between Graph Coloring and Map Coloring?
  • Explain the safety check used in Graph Coloring.
  • What is the worst-case time complexity of Graph Coloring?

🎓 AKTU Examination Tip

AKTU examinations frequently ask students to explain the M-Coloring Problem, write the Backtracking algorithm, solve a small colouring example, draw the State Space Tree and discuss applications such as map colouring, scheduling and register allocation.

Summary

Graph Coloring is a classical Backtracking problem that assigns colours to graph vertices while ensuring that adjacent vertices do not share the same colour. The algorithm explores different colour assignments recursively and backtracks whenever a conflict occurs. It is widely used in map colouring, examination scheduling, compiler optimization, frequency assignment and network resource allocation.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com