dimod.generators.vertex_coloring#

vertex_coloring(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph, colors: Sequence) → BinaryQuadraticModel[source]#

Generate a binary quadratic model (BQM) with ground states corresponding to a vertex coloring.

If \(V\) is the set of nodes, \(E\) is the set of edges and \(C\) is the set of colors the resulting BQM will have:

  • \(|V|*|C|\) variables/nodes

  • \(|V|*|C|*(|C| - 1) / 2 + |E|*|C|\) interactions/edges

The BQM has ground energy \(-|V|\) and an infeasible gap of 1.

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.

  • colors – Color labels to use. The number of colors must be greater or equal to the chromatic number of the graph.

Returns:

A binary quadratic model with ground states corresponding to valid 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.