Graph Vertices Coloring

• Assign a color to each vertex of the graph such that no two adjacent vertices have same color
• Minimum number of color used for proper coloring of a graph is known chromatic number of the graph
• The chromatic number of graph G denoted χ(G), is the smallest k such that G is K-colorable

Facts

• If a G has n vertices, χ(G) <= n
• χ(G)= 1, iff G has on edges
• χ (even-cycle) = 2 and χ(odd-cycle) = 3
• χ(complete G) = n
• if H is a subgraph of then χ(G) >= χ(H)
• For G(V,E) – A K-coloring of G partitions the vertex set V into K sets v1, v2 ……. Vk where each vi is an independent set

Application

• Scheduling is one of its application

Solution:

• For small problem, backtracking approach works, however the graph coloring problem is known as
• NP hard problem.
• Backtracking takk O(m^n) where m => number of color and n=> number of vertices

Algorithm:

• Iterate all color one by one
  • Check is it safe to assign current color for vertex v
  • If yes then
    • assign color to vertex v
    • Recursively call for next vertex

Video

Latest Source Code:
Github: GraphColoring.java

Output:

 Vertex	       Color
0		RED
1		GREEN
2		RED
3		YELLOW