3-colorability
Finding a valid 3-coloring of a graph
In graph theory, the 3-colorability problem is a special case of graph coloring or graph labeling. It is a NP-complete problem.
The goal is as follows: Given an undirected graph G, find an assignment of colors to the nodes out of three colorss so that no adjacent nodes have the same color.
Applications of the 3-colorability problem can be found in scheduling tasks or in social networks.
Taggings:
