def graph_coloring_qubo(graph, k):
K = nx.complete_graph(k)<EOL>g1 = nx.cartesian_product(nx.create_empty_copy(graph), K)<EOL>g2 = nx.cartesian_product(graph, nx.create_empty_copy(K))<EOL>return nx.compose(g1, g2)<EOL>
the QUBO for k-coloring a graph A is as follows:

variables:
x_{v,c} = 1 if vertex v of A gets color c; x_{v,c} = 0 otherwise

constraints:
1)  each v in A gets exactly one color.
   This constraint is enforced by including the term (\sum_c x_{v,c} - 1)^2 in the QUBO,
   which is minimized when \sum_c x_{v,c} = 1.

2) If u and v in A are adjacent, then they get different colors.
   This constraint is enforced by including terms x_{v,c} x_{u,c} in the QUBO,
   which is minimzed when at most one of u and v get color c.

Total QUBO:
Q(x) = \sum_v (\sum_c x_{v,c} - 1)^2  + \sum_{u ~ v} \sum_c x_{v,c} x_{u,c}

The graph of interactions for this QUBO consists of cliques of size k (with vertices {x_{v,c} for c = 0,...,k-1})
plus k disjoint copies of the graph A (one for each color).