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.

  • 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.


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