Coloring

Graph coloring is the problem of assigning a color to the vertices of a graph in a way that no adjacent vertices have the same color.

Example

The map-coloring problem is to assign a color to each region of a map (represented by a vertex on a graph) such that any two regions sharing a border (represented by an edge of the graph) have different colors.

image

Coloring a map of Canada with four colors.

is_vertex_coloring(G, coloring)

Determines whether the given coloring is a vertex coloring of graph G.

min_vertex_color(G[, sampler, chromatic_lb, …])

Returns an approximate minimum vertex coloring.

min_vertex_color_qubo(G[, chromatic_lb, …])

Return a QUBO with ground states corresponding to a minimum vertex coloring.

vertex_color(G, colors[, sampler])

Returns an approximate vertex coloring.

vertex_color_qubo(G, colors)

Return the QUBO with ground states corresponding to a vertex coloring.