(* Testing the 3-colorability of graphs using Grobner bases *)

(* 5-cycle *)
v={1,2,3,4,5};
e = {{1,2},{2,3},{3,4},{4,5},{1,5}};
Graph[v,e]
vars = Table[x[v[[i]]],{i,1,Length[v]}];

polys = Join[Table[x[v[[i]]]^3-1,{i,1,Length[v]}],
Table[x[e[[i,1]]]^2+x[e[[i,1]]]x[e[[i,2]]]+x[e[[i,2]]]^2,{i,1,Length[e]}]]

GroebnerBasis[polys,vars, Modulus->2]

(* Petersen Graph *)
v={1,2,3,4,5,6,7,8,9,10};
e = {{1,2},{2,3},{3,4},{4,5},{1,5},{1,6},{2,7},{3,8},{4,9},{5,10},{6,8},{7,9},{8,10},{9,6},{10,7}};
PetersenGraph[5,2]
vars = Table[x[v[[i]]],{i,1,Length[v]}];

polys = Join[Table[x[v[[i]]]^3-1,{i,1,Length[v]}],
Table[x[e[[i,1]]]^2+x[e[[i,1]]]x[e[[i,2]]]+x[e[[i,2]]]^2,{i,1,Length[e]}]]

GroebnerBasis[polys,vars, Modulus->2]

(* Pinwheel *)
v={1,2,3,4,5,6};
e = {{1,2},{2,3},{3,4},{4,5},{1,5},{1,6},{2,6},{3,6},{4,6},{5,6}};

Graph[v,e]
vars = Table[x[v[[i]]],{i,1,Length[v]}]

polys = Join[Table[x[v[[i]]]^3-1,{i,1,Length[v]}],
Table[x[e[[i,1]]]^2+x[e[[i,1]]]x[e[[i,2]]]+x[e[[i,2]]]^2,{i,1,Length[e]}]]

(* 6-vertex *)
GroebnerBasis[polys,vars, Modulus->2]

v={1,2,3,4,5,6,7};
e = {{1,2},{1,3},{2,3},{2,4},{3,4},{1,5},{1,6},{5,6},{5,7},{6,7},{4,7}};
Graph[v,e]

vars = Table[x[v[[i]]],{i,1,Length[v]}];

polys = Join[Table[x[v[[i]]]^3-1,{i,1,Length[v]}],
Table[x[e[[i,1]]]^2+x[e[[i,1]]]x[e[[i,2]]]+x[e[[i,2]]]^2,{i,1,Length[e]}]]

GroebnerBasis[polys,vars, Modulus->2]