The Graph Coloring represents the painting of the graph or we can say that the labeling of the graph with different types of colors. This technique is very much helpful from the Point of view of differentiating the vertexes from the edges. As in the graph coloring process the adjacent vertexes and the adjacent edges are colored with different colors, the coloring of vertices is called vertex coloring and the coloring of edges is called the edge coloring. Where as the faces of the graph those are sharing the same boundary are colored differently and this is called face coloring.
In mathematics the graph coloring can be expressed as G = (V, E), where ‘G’ represents the graph.
‘V’ represents the vertices and ‘E’ represents 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.
So we can represent it as function F: V®N.
Where the coloring of the vertexes of graph ‘G’ is map and the adjacent vertices has the distinct color in ‘N’, and pq Î E, then F (p) ≠ F (q).
The graph coloring can also be derived with the Graph Coloring algorithm. One of the most common algorithms for the graph coloring is Contraction algorithm. In contraction algorithm for coloring of non- adjacent vertices (p) and (q) we denote G / p, q, the graph ‘G’ is designed by contracting ‘q’ in ‘p’, that is ‘q’ is deleted and the neighbor Set NG (p) of (p) becomes NG(p) È NG(q). In graph coloring the second most common problem is the color selection, that means which face is to be colored by which color, so a solution for this is concluded that we can pick the colors from the flags of the countries and color the graph vertex, edge and faces.
A type of graph, which is in the form of G = (V, E);
Where ‘G’ denotes the graph,
‘V’ denotes the vertices of a graph,
And ‘E’ denotes the edge of a graph is known as bipartite graph. The vertices (V) in the graph are located into two Set X and Y such that each edges is incident to a vertex in X and ‘Y’ vertex, which means there is no two vertices in ‘X’ and ...Read More
Graph coloring is a concept of graph theory, graph (G) is collection of vertices (v1 ,v2, v3....vn) and edges (e1, e2, e3....en), graph coloring means coloring in vertices of graph using minimum number of colors. Color of two adjacent vertices must be different. So we can say that Graph Coloring is the operation on graph. Means two edges of any graph cannot j...Read More