Graph Coloring Problem: Explained

Board Infinity -

Introduction

The graph coloring problem entails assigning colours to specific elements of a graph while adhering to particular limits and constraints. In other terms, Graph coloring refers to the act of assigning colours to vertices so that no two neighbouring vertexes have the same colour.

No two nearby vertices, adjacent edges, or adjacent areas in a graph are coloured with the same number of colours. This is known as the chromatic number, and the graph is known as a properly coloured graph.

Colours, order of coloring, colour assignment, and other constraints are established on the graph while graph coloring. A Color is assigned to a vertex or a specific region. As a result, vertices or areas with the same colour create independent sets.

Vertex coloring

Vertex coloring is the process of assigning colours to the vertices of a graph'G' in such a way that no two adjacent vertices have the same colour. Simply put, no two edge vertices should be the same colour.

Chromatic Number

The chromatic number of G, is the minimal number of colours necessary for vertex coloring of graph and is denoted by X(G)

X(G)=1, if GX is a Null Graph

X(G)>= 2, if GX is not a Null Graph

Region coloring

Colors are assigned to the regions of a planar graph so that no two adjacent regions have the same colour. If two regions share a common edge, they are said to be adjacent.

Example

Take a look at the graph below. As there is a common edge 'be' between those two regions, the regions 'aeb' and 'befc' are adjacent.

Similarly, the other regions are coloured based on their proximity. The colours on this graph are as follows:

Example:

The chromatic number of Kn is

a) n

b) n–1

c) ⌊ n / 2 ⌋

d) ⌈ n / 2 ⌉

Consider this example with K4.

Each vertex in the entire graph is adjacent to the remaining (n - 1) vertices. As a result, each vertex demands a different colour. As a result, the chromatic number is Kn = n.

Method to Colour a Graph

The following are the steps required to colour a graph G with n vertices:

Step 1: Arrange the graph's vertices in some order.

Step 2: Select the first vertex and colour it with the primary colour.

Step 3: Select the next vertex and colour it with the lowest numbered colour that has not yet been coloured on any surrounding vertices. If all of the surrounding vertices are coloured with this colour, change it. Repeat until all of the vertices are coloured.

Example

The first vertex an in the above figure is coloured red. Because the surrounding vertices of vertex an are adjacent once again, vertex b and vertex d are coloured differently, green and blue, respectively. Because no adjacent vertex of c is tinted red, vertex c is coloured red. As a result, we could colour the graph in three different ways. As a result, the graph's chromatic number is 3.

Application of Graph Coloring

One of the most significant notions in graph theory is graph coloring. It is utilised in numerous real-time computer science applications, like :

  • Clustering
  • Data mining
  • Image capturing
  • Image segmentation
  • Networking
  • Resource allocation
  • Processes scheduling

Conclusion

In this article, we have covered what is graph coloring problem, its application. Hope you find this write up knowledgeable.