Graph_Coloring.ipynb

Kernel: Python 2 (SageMath)

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')

  File "<ipython-input-1-68dac69772df>", line 2
    R.<x1,x2,x3,x4,x5,x6,x7,x8> = PolynomialRing(K, order='degrevlex')
      ^
SyntaxError: invalid syntax