dwave_networkx.algorithms.coloring.min_vertex_color¶

min_vertex_color
(G, sampler=None, chromatic_lb=None, chromatic_ub=None, **sampler_args)[source]¶ 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 QUBO [DWMP] with ground states corresponding to minimum vertex colorings and uses the sampler to sample from it.
Parameters:  G (NetworkX graph) – The graph on which to find a minimum vertex coloring.
 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.
 chromatic_lb (int, optional) – A lower bound on the chromatic number. If one is not provided, a bound is calulcated.
 chromatic_ub (int, optional) – 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: 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: References
[DWMP] Dahl, E., “Programming the DWave: Map Coloring Problem”, https://www.dwavesys.com/sites/default/files/Map%20Coloring%20WP2.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.