dwave.graphs.algorithms.coloring.is_vertex_coloring#

is_vertex_coloring(graph: Graph, coloring: dict[Hashable, Hashable]) → bool[source]#

Determines whether the given coloring is a vertex coloring of graph G.

Parameters:

  • graph – The graph on which the vertex coloring is applied.

  • coloring – A coloring of the nodes of graph. Should be a dict of the form {node: color, ...}.

Returns:

True if the given coloring defines a vertex coloring; that is, no two adjacent vertices share a color.

Example

This example colors checks two colorings for a graph, graph, of a single Chimera unit cell. The first uses one color (0) for the four horizontal qubits and another (1) for the four vertical qubits, in which case there are no adjacencies; the second coloring swaps the color of one node.

>>> graph = dwave.graphs.chimera_graph(1,1,4)
>>> colors = {0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1}
>>> dwave.graphs.is_vertex_coloring(graph, colors)
True
>>> colors[4]=0
>>> dwave.graphs.is_vertex_coloring(graph, colors)
False