Strategies and techniques for graph vertex-colouring

Question

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.

Answer 1

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...

Answer 2

This picture should give you an idea.