dwave_networkx.algorithms.coloring.vertex_color

vertex_color(G, colors, sampler=None, **sampler_args)

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 QUBO [DWMP] with ground states corresponding to valid vertex colorings and uses the sampler to sample from it.

Parameters:

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

• colors (int/sequence) – 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 binary quadratic model sampler. A sampler is a process that samples from low energy states in models defined by an Ising equation or a Quadratic Unconstrained Binary Optimization Problem (QUBO). A sampler is expected to have a ‘sample_qubo’ and ‘sample_ising’ method. A sampler is expected to return an iterable of samples, in order of increasing energy. If no sampler is provided, one must be provided using the set_default_sampler function.

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

Returns:

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

Return type:

dict

References

[DWMP]

Dahl, E., “Programming the D-Wave: Map Coloring Problem”, https://www.dwavesys.com/media/htfgw5bk/map-coloring-wp2.pdf

Notes

Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.