dwave.graphs.algorithms.coloring.vertex_coloring#

vertex_coloring(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph, colors: int | Sequence[Hashable], sampler: Sampler, **sampler_args) → dict[Hashable, Hashable][source]#

Returns an approximate 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.

Defines a binary quadratic model with ground states corresponding to valid vertex colorings and uses the 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.

  • colors – The colors. If an int, the colors are labelled [0, n). The number of colors must be greater or equal to the chromatic number of the graph.

  • sampler – A dimod sampler.

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