Sales Toll Free No: 1-855-666-7446

# Graph Coloring

Top
 Sub Topics Graph coloring is defined as coloring the nodes of a graph with the minimum number of colors without any two adjacent nodes having the same color. It is one of the most useful models ingraph theory. It represents the painting of the graph or we can say that the labeling of the graph with different types of colors. It has been used to solve problems in school timetabling, computer register allocation, electronic bandwidth allocation. It has wide applications in estimation of sparse jacobians, scheduling and registering allocation and serves as a model for conflict resolution. Graph coloring technique is very much helpful from the point of view of differentiating the vertices from the edges. While coloring a graph there might be a possibility that we have to face some graph coloring problem like two adjacent edges, vertex or the faces must not be colored evenly, this could mix up that vertex, edges and faces with the adjacent one and this is called graph coloring problem. So each and every adjacent vertex, face and edge should be colored differently.The graph coloring can also be derived with the graph coloring algorithm.

## Graph Coloring Algorithm

Back to Top
There are many heuristic sequential techniques for coloring a graph. Given below are different graph coloring algorithms.

Greed Graph Coloring: This algorithm focuses on carefully picking the next vertex to be colored. In this, once a vertex is colored, its color never changes.
Vertices are considered to be in a specific order $v_{1}, v_{2},........, v_{n}$ and $v_{i}$ is the smallest available color not used by $v_{i}$'s neighbours.
If the vertices are ordered according to their degrees, the resulting greedy coloring uses at most max$_{i}$ min{d(x$_{i}$) + 1, i} colors, at most one more than the graph’s maximum degree.
This heuristic is sometimes called the Welsh–Powell algorithm.
A coloring $F$ of the vertices $v_{0}, v_{1}$,...... ,$v_{n-1}$ of the graph $G$ is tight with respect to the given order, if
$F$($a_{i}$) $\leq$ colors (i - 1) + 1 for all i = 0, 1, ...., n - 1

## Edge Coloring

Back to Top
An edge coloring of a graph G is a coloring of the edges of G such that adjacent edges receive different colors. An edge coloring containing the smallest possible number of colors for a given graph is known as a minimum edge coloring. Whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph.

## Face Coloring

Back to Top
Face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Faces that meet only at a vertex are allowed to be colored the same color. The (face) chromatic number of a map is the smallest number of colors that can be used to color the map subject to our rule, that faces with an edge in common get different colors.

Given below map has been covered with 4 colors.

Although the map above has been colored with 4 colors, this is not the face chromatic number for this map.

The face chromatic number of the map above is, therefore, 3.