Vertex Coloring

Problem Definition

The Vertex Coloring (Coloring) problem is defined on a simple graph. Given k kinds of colors, we need to determine whether we can color all vertices on the graph such that no two adjacent vertices share the same color.

Interfaces

To initialize a Coloring problem, we need to first define a simple graph and decide the number of colors.

julia> using ProblemReductions, Graphs
julia> g = smallgraph(:petersen) # define a simple graph, petersen as example{10, 15} undirected simple Int64 graph
julia> coloring = Coloring{3}(g)Coloring{3, UnitWeight}(SimpleGraph{Int64}(15, [[2, 5, 6], [1, 3, 7], [2, 4, 8], [3, 5, 9], [1, 4, 10], [1, 8, 9], [2, 9, 10], [3, 6, 10], [4, 6, 7], [5, 7, 8]]), [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

We create a petersen graph and take 3 colors here to initialize a Coloring Problem.

Functions variables, flavors, num_flavors, parameters and set_parameters are implemented for Coloring model.

julia> variables(coloring)10-element Vector{Int64}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
julia> flavors(coloring)3-element Vector{Int64}:
 0
 1
 2

Also, evaluate and is_vertex_coloring is also implemented.

julia> is_vertex_coloring(coloring.graph,[1,2,3,1,3,2,1,2,3,1]) #random assignmentfalse