Challenge 8: Graph Coloring
Given a graph, color it in such a way that no adjacent graphs are the same color.
We'll cover the following
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
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.