Graph Coloring | Chromatic Number

Graph Coloring-

 

  • Graph coloring also called as Vertex coloring is a process of assigning colors to all the vertices of the graph such that no two adjacent vertices of it are assigned the same color.
  • In other words, there must not be any edge in the graph whose end vertices are colored with the same color. Such a graph is called as properly colored graph.

 

Example-

 

 

In this graph, no two adjacent vertices have the same color and therefore this graph is a properly colored graph.

 

Applications of Graph Coloring-

 

There are number of applications of graph coloring. Some of them are as follows-

 

  • Map Coloring
  • Scheduling the tasks
  • Preparing Time Table
  • Assignment
  • Conflict Resolution
  • Sudoku

 

Chromatic Number-

 

  • Chromatic Number is the minimum number of colors required to properly color any graph.

OR

  • Chromatic Number is the minimum number of colors required to color any graph such that no two adjacent vertices of it are assigned the same color.

 

Example-

 

Consider the following graph-

 

In this graph, no two adjacent vertices have the same colors and the minimum number of colors = 3 have been used to color the vertices.

Therefore,

Chromatic number of this graph = 3

 

We can not properly color this graph with less than 3 colors.

 

Common Types of Graphs and their Chromatic numbers-

 

1. Cycle Graphs-

 

A simple graph having ‘n’ vertices (n>=3) and n edges is called a cycle graph if all its edges form a cycle of length ‘n’.

OR

A cycle graph is a graph where degree of each vertex is 2.

 

Chromatic Number

  • If number of vertices in cycle graph is even, then its chromatic number = 2
  • If number of vertices in cycle graph is odd, then its chromatic number = 3

 

Examples-

 

 

2. Planar Graphs-

 

A planar graph is a graph that can be drawn in a plane such that none of its edges cross each other.

 

Chromatic Number

Chromatic Number of Planar Graphs = Less than or equal to 4

 

Examples-

 

All the above cycle graphs are also planar graphs where chromatic number of each graph is less than or equal to 4.

 

3. Complete Graphs-

 

  • A complete graph is a graph in which every two distinct vertices are joined by exactly one edge.
  • In a complete graph, because each vertex is connected with every other vertex, so we need as many different colors as there are number of vertices in the given graph in order to properly color the graph.

 

Chromatic Number

Chromatic Number of Complete Graphs = Number of vertices in the Complete Graph

 

Examples-

 

 

4. Bipartite Graphs-

 

A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.

 

Chromatic Number

Chromatic Number of Bipartite Graphs = 2

 

Example-

 

 

5. Trees-

 

  • A tree is a special type of connected graph in which there are no circuits.
  • Every tree is a bipartite graph, so chromatic number of tree with n vertices = 2.

 

Chromatic Number

Chromatic Number of any tree = 2

 

Examples-

 

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Graph Coloring | Chromatic Number
Article Name
Graph Coloring | Chromatic Number
Description
Graph coloring is a process of assigning colors to all the vertices of the graph such that no two adjacent vertices are assigned the same color. Chromatic Number is the minimum number of colors required to properly color the graph. Chromatic Number of cycle graph, bipartite graph, planar graph, complete graph, tree.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-