# dwave_networkx.algorithms.coloring.vertex_color_qubo¶

vertex_color_qubo(G, colors)[source]

Return the QUBO with ground states corresponding to a vertex coloring.

If V is the set of nodes, E is the set of edges and C is the set of colors the resulting qubo will have:

• $$|V|*|C|$$ variables/nodes

• $$|V|*|C|*(|C| - 1) / 2 + |E|*|C|$$ interactions/edges

The QUBO has ground energy $$-|V|$$ and an infeasible gap of 1.

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.

Returns

QUBO – The QUBO with ground states corresponding to valid colorings of the graph. The QUBO variables are labelled (v, c) where v is a node in G and c is a color. In the ground state of the QUBO, a variable (v, c) has value 1 if v should be colored c in a valid coloring.

Return type

dict