Graph_Coloring.sagews

This is a slightly modified copy of a sage worksheet that was written by Stefan van der Lugt

Exercise 3

(Graph coloring) A graph is an ordered pair $G=(V,E)$, with $V$ a set of vertices, and $E$ a set of edges, which are 2-element subsets of $V$. An $n$-coloring of a graph $G$ is an assignment of one of $n$ colors to each vertex of $G$ in such a way that any two vertices connected by an edge have distinct colors. In this exercise we will assume that $G$ has finitely many edges, and we will label the vertices by the set $V=\{1,2,\dots,N\}$.

Let $K$ be any field with at least $n$ elements, and let $S\subset K$ be a subset with $n$ elements. These elements will represent the $n$ colors. An $n$-coloring of $G$ is then equivalent to assigning a value $x_i = \alpha_i$ for $i=1,\dots,N$ (giving each vertex a color) such that $\alpha_i \neq \alpha_j$ for each edge $\{i,j\}\in E$ (making sure adjacent vertices have distinct colors).

Let $f(x) = \prod_{i=1}^n (x - \alpha_i)$, and $g(x,y) = (f(x)-f(y))/(x-y)$.

• ($i$) Show: $g(x,y)$ is a polynomial in $K[x,y]$, and show that giving an $n$-coloring of $G$ is equivalent to solving the following system of equations in $N$ variables $x_1,\dots,x_N$: $$\begin{cases} f(x_i) = 0 & \text{for all }i=1,\dots,N \\ g(x_i,x_j) = 0 & \text{for every edge }\{i,j\}\text{ of }G \end{cases}$$

• ($ii$) Show that an $n$-coloring for $G$ exists if and only if the ideal $$I = ( \{f(x_i): i=1,\dots,N\} \cup \{g(x_i,x_j): \{i,j\}\in E\} )_{K[x_1,\dots,x_N]} \subset K[x_1,\dots,x_N]$$ is proper.

This allows us to use software capable of working with Gr"obner bases to find information about coloring of finite graphs.

• ($iii$) Consider the graph $G$ with eight vertices and 14 edges $\{1,3\}$, $\{1,4\}$, $\{1,5\}$, $\{2,4\}$, $\{2,7\}$, $\{2,8\}$, $\{3,4\}$, $\{3,6\}$, $\{3,8\}$, $\{4,5\}$, $\{5,6\}$, $\{6,7\}$, $\{6,8\}$, $\{7,8\}$. Show that, up to permutation of the colors, $G$ has a unique $3$-coloring. (Hint: consider $K=\mathbb{F}_3$ with colors $0,1,2\in\mathbb{F}_3$. We may without loss of generality assume that vertex 1 will get color 0, and the adjacent vertex 3 will get color 1. Use computer software to compute a (reduced) Gr"obner basis for the ideal generated by the $f(x_i)$, $g(x_i,x_j)$ and $x_1-0$ and $x_3-1$).

• ($iv$) Use Gröbner bases to show that the graph $G$ with nine vertices and 22 edges $(1,4)$, $(1,6)$, $(1,7)$, $(1,8)$, $(2,3)$, $(2,4)$, $(2,6)$, $(2,7)$, $(3,5)$, $(3,7)$, $(3,9)$, $(4,5)$, $(4,6)$, $(4,7)$, $(4,9)$, $(5,6)$, $(5,7)$, $(5,8)$, $(5,9)$, $(6,7)$, $(6,9)$, $(7,8)$ has precisely four 4-colorings up to permutations of the colors. Show that if the edge $(1,5)$ is added then $G$ cannot be 4-colored.

---

Exercise 3($iii$) of week 12

Consider the graph $G$ with eight vertices and 14 edges $\{1,3\}$, $\{1,4\}$, $\{1,5\}$, $\{2,4\}$, $\{2,7\}$, $\{2,8\}$, $\{3,4\}$, $\{3,6\}$, $\{3,8\}$, $\{4,5\}$, $\{5,6\}$, $\{6,7\}$, $\{6,8\}$, $\{7,8\}$. Show that, up to permutation of the colors, $G$ has a unique $3$-coloring.

First, we define our field $K = \mathbb{F}_3$, and our polynomial ring $R$ over $K$ with 8 variables $x_1, \dots, x_8$.

We also fix a monomial ordering on R, the degrevlex/grevlex ordering.

K = FiniteField(3)
R.<x1,x2,x3,x4,x5,x6,x7,x8> = PolynomialRing(K, order='degrevlex')

Now, we define the polynomials $f(x) = (x-0)(x-1)(x-2)$ and $g(x,y) = \frac{f(x)-f(y)}{x-y}=x^2+xy+y^2 - 1$.

f(x)=x*(x-1)*(x-2)
g(x,y)=x^2+x*y+y^2-1

Now we define the ideal $I\subseteq R$ generated by the polynomials $f(x_i)$ for $i=1,\dots,8$ and $g(x_i,x_j)$ for $\{i,j\}\in E$.

I=R.ideal(f(x1), f(x2), f(x3), f(x4), f(x5), f(x6), f(x7), f(x8), g(x1,x3), g(x1,x4), g(x1,x5), g(x2,x4), g(x2,x7), g(x2,x8), g(x3,x4), g(x3,x6), g(x3,x8), g(x4,x5), g(x5,x6), g(x6,x7), g(x6,x8), g(x7,x8))

Now we compute a Gröbner basis for $I$.

I.groebner_basis()

[x8^3 - x8, x7^2 + x7*x8 + x8^2 - 1, x1 + x7 + x8, x2 + x7 + x8, x3 - x7, x4 - x8, x5 - x7, x6 + x7 + x8]

Notice that finding a common zero of the polynomials in this Gröbner basis is equivalent to finding a solution to the equations $f(x_8)=x_8^3 - x_8 = 0$ and $g(x_7,x_8)=x_7^2 + x_7 x_8 + x_8^2 - 1 = 0$ induced by the first two elements of this basis. The other elements of the Gröbner basis give linear equations for $x_1,\dots,x_6$ with unique solutions that depend only on $x_7$ and $x_8$.

Finding a solution to $f(x_8)=0$ and $g(x_7,x_8)=0$, that is, choosing a color for vertex 8 and a different color for the adjacent vertex 7, determines a unique 3-coloring for the rest of the graph. This shows that there exist 6 distinct colorings of the graph, and these 6 colorings are in fact the same up to a permutation of the colors.

For example, if we choose color 0 for vertex 8 (that is, adding the polynomial $x_8-0$ to our ideal), we get the following Gröbner basis.

(I+R.ideal(x8)).groebner_basis()

[x7^2 - 1, x1 + x7, x2 + x7, x3 - x7, x4, x5 - x7, x6 + x7, x8]

The only non-linear polynomial in this basis is $x_7^2 - 1$, which has roots $x_7=1$ and $x_7=2$. Translating this to graph theory: after choosing color 0 for vertex 8, we can choose color 1 or 2 for vertex 7, and this will determine the color of vertices $1,\dots,6$ uniquely.

For example, if we now pick color 1 for vertex 7, we find the following Gröbner basis.

(I+R.ideal(x8,x7-1)).groebner_basis()

[x6^3 + x6^2 + x6, x3^2 + x3*x5 + x3, x5^2 + x5 + 1, x5*x6 + x6^2 + x6, x1 + x5, x2 + x5, x4 + x5 + x6 + 1, x7 + 1, x8, x9 + 1]

The roots of these polynomials, and thus the colors of the other vertices, can be read off easily now. The vertices $x_4$ and $x_8$ have color 0, the vertices $x_3$, $x_5$ and $x_7$ have color 1, and the vertices $x_1$, $x_2$ and $x_6$ have color 2.

Instead of picking a color for vertex 8, we could also start by picking a color for vertex 1. Let's try giving vertex 1 color 0.

(I+R.ideal(x1)).groebner_basis()

[x9^3 + 1, x3^2 + x3*x9 + x9^2, x6^2 + x6*x9 + x9^2, x8^2 + x8*x9 + x9^2, x1, x2, x4 + x6 + x9, x5, x7 + x9]

This already shows that vertex 2 and vertex 6 will also have color 0, and vertex 8 cannot have color 0 anymore.

If we didn't notice this and accidentally try to color vertex 2 a different color, we will get the following Gröbner basis.

(I+R.ideal(x1,x2-1)).groebner_basis()

[1]

Clearly the elements of this Gröbner basis do not have a common zero! This means that there is no possible coloring of $G$ such that vertex 1 has color 0 and vertex 2 has color 1.

So instead of deliberately giving vertex 2 the wrong color, let's pick color 1 for vertex 3.

(I+R.ideal(x1,x3-1)).groebner_basis()

[x1, x2, x3 - 1, x4 + 1, x5 - 1, x6, x7 - 1, x8 + 1]

This gives a unique coloring for the rest of the graph: one easily reads off from this basis that $x_1$, $x_2$ and $x_6$ have color 0, $x_3$, $x_5$ and $x_7$ have color 1, and $x_4$ and $x_8$ have color 2. This coloring differs from the previously found coloring only by a permutation of the colors.

Let's see what happens if we add an extra edge, say between vertex 5 and vertex 7.

(I+R.ideal(g(x5,x7))).groebner_basis()

[1]

This shows that we can't equip this graph with a 3-coloring anymore. This is as one would expect: in any coloring of the original graph vertices 5 and 7 have the same color.

---

Exercise 3.(iv)

Use Gröbner bases to show that the graph $G$ with nine vertices and 22 edges $(1,4)$, $(1,6)$, $(1,7)$, $(1,8)$, $(2,3)$, $(2,4)$, $(2,6)$, $(2,7)$, $(3,5)$, $(3,7)$, $(3,9)$, $(4,5)$, $(4,6)$, $(4,7)$, $(4,9)$, $(5,6)$, $(5,7)$, $(5,8)$, $(5,9)$, $(6,7)$, $(6,9)$, $(7,8)$ has precisely four 4-colorings up to permutations of the colors. Show that if the edge $(1,5)$ is added then $G$ cannot be 4-colored.

We will work with the field $K=\mathbb{F}_4$ of 4 elements; this field is obtained from $\mathbb{F}_2$ by adjoining a root of the irreducible polynomial $x^2+x+1$. We could of course work with $\mathbb{F}_5$ as well.

We have: $f(x) = x(x-1)(x-a)(x-a-1) = x^4+x$, and

$$g(x,y) = \frac{f(x)-f(y)}{x-y} = x^3 + x^2 y + xy^2 + y^3 + 1 \in \mathbb{F}_4[x,y]$$

The graph $G$ has nine vertices, so we define $R = K[x_1,\dots,x_9]$.

K.<a> = FiniteField(4,'a')
f(x) = x*(x-1)*(x-a)*(x-a-1)
g(x,y) = x^3 + x^2*y + x*y^2 + y^3 + 1
R.<x1,x2,x3,x4,x5,x6,x7,x8,x9> = PolynomialRing(K, order='degrevlex')

The ideal $I$ is generated by the $f(x_i)$ for $i=1,\dots, 9$ and $g(x_i,x_j)$ for all $(i,j)\in E$.

I = R.ideal(f(x1), f(x2), f(x3), f(x4), f(x5), f(x6), f(x7), f(x8), f(x9), g(x1,x4), g(x1,x6), g(x1,x7), g(x1,x8), g(x2,x3), g(x2,x4), g(x2,x6), g(x2,x7), g(x3,x5), g(x3,x7), g(x3,x9), g(x4,x5), g(x4,x6), g(x4,x7), g(x4,x9), g(x5,x6), g(x5,x7), g(x5,x8), g(x5,x9), g(x6,x7), g(x6,x9), g(x7,x8))
I.groebner_basis()

[x9^4 + x9, x6^3 + x6^2*x9 + x6*x9^2 + x9^3 + 1, x8^3 + x8^2*x9 + x8*x9^2 + x9^3 + 1, x3^2 + x3*x5 + x5*x8 + x8^2 + x3*x9 + x8*x9, x5^2 + x5*x8 + x8^2 + x5*x9 + x8*x9 + x9^2, x5*x6 + x6^2 + x5*x8 + x8^2 + x6*x9 + x8*x9, x1 + x5, x2 + x5, x4 + x5 + x6 + x9, x7 + x9]

We want to find the number of colorings of $G$ up to permutation of colors, so we might as well give vertex 9 color 0.

(I+R.ideal(x9)).groebner_basis()

[x6^3 + 1, x8^3 + 1, x3^2 + x3*x5 + x5*x8 + x8^2, x5^2 + x5*x8 + x8^2, x5*x6 + x6^2 + x5*x8 + x8^2, x1 + x5, x2 + x5, x4 + x5 + x6, x7, x9]

The sixth vertex, which is adjacent to vertex 9, can be given any color except for color 0. In the above Gröbner basis this statement corresponds to the equation $x_6^3+1=0$.

We may therefore assume that vertex 6 gets color 1.

(I+R.ideal(x9,x6-1)).groebner_basis()

[x8^3 + 1, x3^2 + x3*x5 + x5 + 1, x5^2 + x5 + 1, x5*x8 + x8^2 + x5 + 1, x1 + x5, x2 + x5, x4 + x5 + 1, x6 + 1, x7, x9]

After choosing color 0 for vertex 9 and color 1 for vertex 6 we make the following observation: the colors of vertices 6, 7 and 9 are determined. The color of vertex 5 is $a$ or $a+1$. Choosing a color for vertex 5 uniquely determines the colors of vertices 1, 2, and 4.

By symmetry, we may assume that vertex 5 has color $a$. This removes the final degree of freedom induced by permutations of colors.

(I+R.ideal(x9,x6-1,x5-a)).groebner_basis()

[x3^2 + (a)*x3 + (a + 1), x8^2 + (a)*x8 + (a + 1), x1 + (a), x2 + (a), x4 + (a + 1), x5 + (a), x6 + 1, x7, x9]

We now find:

• Vertices 7 and 9 have color 0

• Vertex 6 has color 1

• Vertices 1, 2, and 5 have color $a$

• Vertex 4 has color $a+1$

• $x_3^2 + ax_3 + (a+1) = (x_3+1)(x_3+a+1) = 0$, so $x_3$ has color 1 or color $a+1$

• $x_8^2 + ax_8 + (a+1) = 0$, so $x_8$ has color 1 or color $a+1$.

In particular: even after fixing a permutation of the colors, we are still able to choose between two colors for both vertex 3 and vertex 8. This shows that $G$ has precisely $2\cdot 2=4$ unique 4-colorings up to permutation of colors.

Let's add edge $(1,5)$ to our graph and see what happens.

(I+R.ideal(g(x1,x5))).groebner_basis()

[1]

This proves that the graph obtained from $G$ by adding the edge $(1,5)$ does not have a 4-coloring.