dwave_networkx.algorithms.coloring.is_vertex_coloring#

is_vertex_coloring(G, coloring)[source]#

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

Parameters:

  • G (NetworkX graph) – The graph on which the vertex coloring is applied.

  • coloring (dict) – A coloring of the nodes of G. Should be a dict of the form {node: color, …}.

Returns:

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

Return type:

bool

Example

This example colors checks two colorings for a graph, G, 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.

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