Description: A known problem in graph theory , 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.
The problem consists of an undirected graph G=(V,E) is a map c: V -> S such that c(u) != c(v) whenever there exists an edge (u,v) in G.
(where āSā is a finite set of colors.)

The problem is to determine the minimum cardinality (the number of colors) of S for a given graph G or to ask whether it is able to color graph G with a certain number of colors. For example, how many color do we need to color the United States on a map in such a way that adjacent states have different color?

However, coloring a general graph with the minimum number of colors (the cardinality of set S) is known to be an NP-complete problem. One often relies on heuristics to find a solution. A widely-used general greedy based approach is starting from an ordered vertex enumeration V1, ..., Vn of G, to assign Vi to the smallest possible color for i from 1 to n.

Applications: estimation of sparse Jacobins,scheduling, registering allocation, optimization and parallel numerical computation.

Algorithmic problem:
Input - a graph (V,E),C
V - set of Vertices
E - set of Edges <= VxV
c - set of Colors

Output - boolean - can he graph be colored following the rules using the set of colors?
True or False

Algorithmic Solution: (1) In case you would like to dermine if a graph can be colored with 2 colors, you are actually asking yourself whether the graph is bipartite, and thus polynomial time-computable.

(2) Brute force for |S| = k colors considers every of the (n over k) assignments of colors to vertices and checks for each if it is legal.

(3) Greedy algorithm , This technique focuses on carefully picking the next vertex to be colored. In this heuristic algorithm, once a vertex is colored, its color never changes.

Heuristics: When using a Greedy algorithm one need to define the method of picking the next vertex, In this case the Heuristic is the way of picking the next vertex:

Description:A known problem in graph theory , 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.The problem consists of an undirected graph G=(V,E) is a map c: V -> S such that c(u) != c(v) whenever there exists an edge (u,v) in G.

(where āSā is a finite set of colors.)

The problem is to determine the minimum cardinality (the number of colors) of S for a given graph G or to ask whether it is able to color graph G with a certain number of colors. For example, how many color do we need to color the United States on a map in such a way that adjacent states have different color?

However, coloring a general graph with the minimum number of colors (the cardinality of set S) is known to be an NP-complete problem. One often relies on heuristics to find a solution. A widely-used general greedy based approach is starting from an ordered vertex enumeration V1, ..., Vn of G, to assign Vi to the smallest possible color for i from 1 to n.

Applications:estimation of sparse Jacobins,scheduling, registering allocation, optimization and parallel numerical computation.Algorithmic problem:Input - a graph (V,E),C

V - set of Vertices

E - set of Edges <= VxV

c - set of Colors

Output - boolean - can he graph be colored following the rules using the set of colors?

True or False

Algorithmic Solution:(1) In case you would like to dermine if a graph can be colored with 2 colors, you are actually asking yourself whether the graph is bipartite, and thus polynomial time-computable.

(2) Brute force for |S| = k colors considers every of the (n over k) assignments of colors to vertices and checks for each if it is legal.

(3) Greedy algorithm , This technique focuses on carefully picking the next vertex to be colored. In this heuristic algorithm, once a vertex is colored, its color never changes.

Heuristics:

When using a Greedy algorithm one need to define the method of picking the next vertex, In this case the Heuristic is the way of picking the next vertex:

1) First Fit

2) Degree based ordering

Reference:New Graph Coloring Algorithms by Dr. Hussein Al-Omari and Khair Eddin Sabri