Graph coloring

The problem consists on assigning colors to the nodes in a graph while taking care never to assign the same color to nodes that share an edge (or arc). The objective is to use the least number of different colors to succesfully color the whole graph.

Name of dag: graph_coloring

Available solution methods:

  • default: CP model built in ortools with CP-SAT as solver.

Decision

For each node x, its color p.

Colors are represented as an integer number.

Parameters

  • Edges of the graph.