# Strategies and techniques for graph vertex-colouring

What are the most effective techniques and strategies for vertex-colouring?

What are the most basic approaches to vertex-colouring a plane graph in particular. I have a family of planar graphs I believe are three colourable but I am not sure how to start a working proof. Surely if $G$ is planar and $\chi (G)$ is the chromatic number of $G$ then $\chi (G)<5$. We also have Grötzsch's theorem.

## 2 Answers

You can Use Gröbner bases to construct the colorings of a finite graph. I cite:

... It turns out that we can represent every graph coloring as a solution to a carefully chosen system of polynomial equations. Conversely, given a finite graph G, we can construct a system of polynomial equations whose solutions are the colorings of G....

In the 3-colour case:

Let there be a field $F = \mathbb{Z}/3\mathbb{Z}$ and let $S = F = \{0,1,2\}$ be our set of colors. There are two types of polynomials on $F$:

• $f(z) = z(z-1)(z-2) = z^3-z$
• $g(y,w) = y^2+yw+w^2-1$.

Let $I$ be the ideal $I = (x_t^3-x_t \ |\ t \in [1,n]) + (x_r^2+x_rx_s+x_s^2-1 \ |\ \{r,s\} \in E)$. Now find a Gröbner basis with Buchbergers Algorithm and you're done.

But to be honest, for me as well this is still theory. Here's my own question/answer on that topic...

• What is $E$? And what about it is still theory? Have you looked into using this technique to prove an already known problem. For example triangle free plane graphs? – Antonio Hernandez Maquivar Oct 4 '16 at 13:03
• $E$ is the set of edges. I never wrote an implementation of the algorithm to get result, so "No" I never did. But the linked answer shows how to use in Maple or Singular... – draks ... Oct 4 '16 at 13:06
• It seems as though this would be a good approach to colour a specific graph but what would be the approach to a family of graphs? I guess I might prove a few base example explicitly and then add edges incrementally? – Antonio Hernandez Maquivar Oct 4 '16 at 13:14
• @AnthonyHernandez what's that family? Triangle free plane graphs? I think the answer depends heavily on the structure in that family and colouring might change dramatically for certain examples when you add on edge. Like factorisation of a number might change dramatically if you add 1, e.g. $6=2\cdot 3$ and $6+1=7$... – draks ... Oct 4 '16 at 14:23
• I am interested in colouring the following family of graphs: Let $A_n$ be a simple arrangement of lines in the Euclidean plane. Circumscribe the arrangement so that all intersection occur in the interior of the circle. Denote the circumscribed arrangement by $G$. A vertex in $G$ is any point where two lines intersect or where a line intersects the boundary of the circle. Edges are defined intuitively. I claim that $\chi(G)=3$. Explicitly I know the exact number of vertices, edges and faces of $G$. I even know that $G$ Hamiltonian. $G$ is planar by definition. It is not triangle free. – Antonio Hernandez Maquivar Oct 4 '16 at 14:33 This picture should give you an idea.