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.


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

  • $\begingroup$ 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? $\endgroup$ – Antonio Hernandez Maquivar Oct 4 '16 at 13:03
  • 1
    $\begingroup$ $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... $\endgroup$ – draks ... Oct 4 '16 at 13:06
  • $\begingroup$ 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? $\endgroup$ – Antonio Hernandez Maquivar Oct 4 '16 at 13:14
  • $\begingroup$ @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$... $\endgroup$ – draks ... Oct 4 '16 at 14:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Antonio Hernandez Maquivar Oct 4 '16 at 14:33

This did not fit in the comment section but it should give you an idea.

This picture should give you an idea.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.