Graph coloring Algorithm

Question

From wiki http://en.wikipedia.org/wiki/Graph_coloring

In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a 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.

Given 'n' colors and 'm' vertices, how easily can a graph coloring algorithm be implemented in a programming language?

Language no barrier.

Just a brain teaser.

(Assume Graph and vertex objects exist)

Edit:
After reading wiki , the problem is NP-complete
Time to revisit maths books :)
my bad.
sorry.

Just curious,
Has this been tried ? as in writing programs for same?
I heard that this is used in optical networks?

Isn't this similar to cube coloring??
(minimum number of colors to color faces of cube so that no two sides share the same color?)

Answer 1

It's an NP complete problem, read the Wikipedia entry for more information on various methods of solving.

Answer 2

If you are given 2 colors, and the graph is 2-colorable (i.e. it's a bipartite graph), then you can do it in polynomial time quite trivially.

I gave a pseudocode as answer to this question: Graph colouring algorithm: typical scheduling problem.

Answer 3

As mentioned, the general problem is np-complete. Bipartite graphs can be colored using only 2 colors.

It is also true that planar graphs (graphs that do not contain K3,3 or K5 as sub graphs, as per Kuratowski's theorem) can be colored with 4 colors.