dwave.graphs.algorithms.coloring.min_vertex_coloring

min_vertex_coloring(graph: Graph, sampler: Sampler, chromatic_lb: int | None = None, chromatic_ub: int | None = None, **sampler_args) → dict[Hashable, Hashable]

Returns an approximate 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 binary quadratic model with ground states corresponding to minimum vertex colorings and uses the sampler to sample from it.

Parameters:

• graph – The graph on which to find a minimum vertex coloring.

• sampler – A dimod sampler.

• 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.

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

Returns:

A coloring for each vertex in graph such that no adjacent nodes share the same color. A dict of the form {node: color, ...}.