dimod.generators.min_vertex_coloring#

min_vertex_coloring(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph, chromatic_lb: int | None = None, chromatic_ub: int | None = None) → BinaryQuadraticModel[source]#

Generate a binary quadratic model (BQM) 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.

After defining a BQM/QUBO [Dah2013] with ground states corresponding to minimum vertex colorings, use a sampler to sample from it.

Parameters:

  • graph – The graph on which to find a vertex coloring. Either an integer n, interpreted as a complete graph of size n, a nodes/edges pair, a list of edges or a NetworkX graph.

  • chromatic_lb – A lower bound on the chromatic number. If one is not provided, a bound is calculated.

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

Returns:

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