Challenge: Graph Coloring

Problem Statement

Graph coloring involves finding a way of coloring the vertices of a graph.

Implement a function that finds a way of coloring a graph so that no two adjacent vertices are colored using the same color. Try using the minimum possible colors.

Input

An undirected graph with no colors assigned

Output

A graph with all vertices colored in the correct way, using the minimum number of colors possible

Sample Input

Graph:

graph {0 -- 1
       0 -- 2
       1 -- 2
       1 -- 3
       2 -- 3
       3 -- 4}

Sample Output

Vertex 0 ---> Color 0
Vertex 1 ---> Color 1
Vertex 2 ---> Color 2
Vertex 3 ---> Color 0
Vertex 4 ---> Color 1