Graph Coloring

The graph coloring problem (GCP), also known as vertex coloring problem, requires to find an assignment of colors to vertices of a graph such that no two adjacent vertices share the same color while minimizing the number of colors. GCP is a fundamental combinatorial optimization problem and is NP-hard.

Solvers for GCP

FastColor is a graph coloring solver for coloring massive graphs within short time. It interleaves between graph reduction and bound computation.
---Reference: Jinkun Lin, Shaowei Cai, Chuan Luo, Kaile Su: A Reduction based Method for Coloring Very Large Graphs. In Proc. of IJCAI 2017: 517-523

Return to homepage.