In [ ]:

    

from sympy import *
init_printing(use_latex=True)


    

In [ ]:

    

import networkx as nx


    

In [ ]:

    

V = range(1, 12+1)


    

In [ ]:

    

E = [(1,2),(2,3),(1,4),(1,6),(1,12),(2,5),(2,7),(3,8),(3,10),(4,11),(4,9),(5,6),
     (6,7),(7,8),(8,9),(9,10),(10,11),(11,12),(5,12),(5,9),(6,10),(7,11),(8,12)]


    

In [ ]:

    

g = nx.Graph()
g.add_nodes_from(V)
g.add_edges_from(E)


    

In [ ]:

    

import bokeh.plotting as plt
plt.output_notebook()

def nx_draw(g, layout=nx.circular_layout, node_color="white", text_color="black"):
    pos = layout(g)
    xs, ys = [], []
    labels = [ str(v) for v in g.nodes() ]
    vx, vy = zip(*[ pos[v] for v in g.nodes() ])
    for (a, b) in g.edges():
        x0, y0 = pos[a]
        x1, y1 = pos[b]
        xs.append([x0, x1])
        ys.append([y0, y1])
    f = plt.figure(width=300, height=300, x_axis_type=None, y_axis_type=None,
                   outline_line_color=None, toolbar_location=None)
    f.multi_line(xs, ys, line_color="black")
    f.circle(vx, vy, size=16, line_color="black", fill_color=node_color)
    f.text(vx, vy, text=labels, text_color=text_color, text_font_size="10px",
           text_align="center", text_baseline="middle")
    return f


    

In [ ]:

    

plt.show(nx_draw(g))


    

In [ ]:

    

Vx = [ var('x%d' % i) for i in V ]
Ex = [ (Vx[i-1], Vx[j-1]) for i, j in E ]
F3 = [ xi**3 - 1 for xi in Vx ]
Fg = [ xi**2 + xi*xj + xj**2 for xi, xj in Ex ]
Fx = F3 + Fg


    

In [ ]:

    

G = groebner(Fx, order='lex')


    

In [ ]:

    

colors = var('red,green,blue')
roots_of_unity = roots(Dummy()**3 - 1, multiple=True)
color_map = dict(zip(roots_of_unity, colors))


    

In [ ]:

    

solutions = solve(G, *Vx)


    

In [ ]:

    

colorings = [ [ color_map[zeta] for zeta in solution ] for solution in solutions ]


    

In [ ]:

    

plots = []
for i, coloring in enumerate(colorings):
    f = nx_draw(g, node_color=[ str(color) for color in coloring ], text_color="white")
    if i % 2 == 0:
        plots.append([f])
    else:
        plots[-1].append(f)
plt.show(plt.gridplot(plots, toolbar_location=None))


    

In [ ]: