Skip to main content

What is graph coloring and why we use it ??????

Graph coloring is nothing but a simple way of labelling graph components such as vertices, edges, and regions under some constraints. In a graph, no two adjacent vertices, adjacent edges, or adjacent regions are colored with minimum number of colors.
This number is called the chromatic number and the graph is called a properly colored graph.

Why it is used :

Graph colouring refers to the property of some networks to have their vertex sets consist of subsets such that there are no connections between nodes belonging to the same sets. If there are two such sets, the graph is refered to as a bipartite network. If there are k such sets, then the network is called k-partite. So graph colouring is used to distinguish between memership to different sets. You can confirm that there are no direct connections between nodes beloning to the same sets.

Posted by -