dwave_networkx.algorithms.coloring.min_vertex_color_qubo#

min_vertex_color_qubo(G, chromatic_lb=None, chromatic_ub=None)[source]#

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

Vertex 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. A minimum vertex coloring is the problem of solving the vertex coloring problem using the smallest number of colors.

Defines a QUBO [DWMP] with ground states corresponding to minimum vertex colorings and uses the sampler to sample from it.

Parameters:

  • G (NetworkX graph) – The graph on which to find a minimum vertex coloring.

  • chromatic_lb (int, optional) – A lower bound on the chromatic number. If one is not provided, a bound is calulcated.

  • chromatic_ub (int, optional) – An upper bound on the chromatic number. If one is not provided, a bound is calculated.

  • sampler_args – Additional keyword parameters are passed to the sampler.

Returns:

QUBO – The QUBO with ground states corresponding to minimum colorings of the graph. The QUBO variables are labelled (v, c) where v is a node in G and c is a color. In the ground state of the QUBO, a variable (v, c) has value 1 if v should be colored c in a valid coloring.

Return type:

dict