27
$\begingroup$

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph is 5-colorable. It's rather simple to prove Five Color Theorem in a standard mathematical approach (without resort to computers) and many graph theory textbooks explain this proof based on induction. (Even the wikipedia article covers the proof.)

Now, I'm interested in an algebraic proof of Five Color Theorem using chromatic polynomials. Let $\pi_G(x)$ be a chromataic polynomial of a graph $G$. The Five Color Theorem is proved once $\pi_G(5) > 0$ is shown for any planar graph $G$ because $\pi_G(5)$ is the number of 5-colorings of a graph $G$. In fact, Birkhoff introduced the chromatic polynomial with the hope of proving the Four Color Theorem by showing that $\pi_G(4) > 0$ for any planar graph. This approach was in vain, yet he and Lewis succeeded in showing that $\pi_G(x) > 0$ for any planar graph $G$ when $x$ is a real number larger than or equal to 5. For this algebraic proof of Five Color Theorem, many people point to 97-page paper written by Birkhoff and Lewis in 1946.


As a computer science TA of an advanced graph theory course, I think this algebraic proof is worth for a brief explanation and may be an adequate thesis topic for master student or even an undergraduate student. But it's somewhat hard to find out which part of the 97 page document is about an algebraic proof of Five Color Theorem. (Probably it's because I'm not a native speaker and not familiar with paper writing styles almost 70 years ago.)

  1. Is there anyone who already read Birkhoff and Lewis and can tell me which section is about the actual algebraic proof?
  2. Is there any other recent lecture notes or textbooks explaining this algebraic proof in a concise fashion?
$\endgroup$
33
$\begingroup$

I tried to go through Birkhoff and Lewis many years ago but it is not easy because they use different variables and the style is so different to modern proofs.

In modern terms, the key idea is that if a graph contains a vertex $v$ of degree k, then you can get an expression of the form $$P(G,\lambda) = (\lambda-k) P(G-v,\lambda) + \text{other terms}$$ where the other terms are all chromatic polynomials of minors of $G$.

So if the inductive hypothesis is that $P(G,x)> 0$ for all $x\geq 5$, then this reduction gives the inductive step.

Then we know that any planar graph has a vertex of degree at most 5, and that a minor of a planar graph is planar, and so we're done.

The expression involving $(\lambda-k)$ was proved by Thomassen, separately by Woodall, and more generally for all matroids by Oxley whose result preceded the others by two decades. However, although he proved the result, Oxley didn't actually state it explicitly, so missing it can be excused.

I'll dig out the BL paper tomorrow and see if their approach was essentially the same.

Added I think that the result is contained in Theorem 3.1 on page 413 in the BL paper (freely available from AMS), which bounds the coefficients of a polynomial $Q$ (the chromatic polynomial after a few trivial factors are removed). They helpfully remark that in this chapter, their usage of the symbol $\ll$ is "contrary to the notation of the preceding chapter", presumably to prevent any complacency on the part of the reader.

$\endgroup$
  • $\begingroup$ I do not understand the formulation of Oxley's result for matroids. What does it mean 'remove a vertex'? $\endgroup$ – Fedor Petrov Apr 15 '16 at 18:08
  • $\begingroup$ @Fedor - removing (deleting and contracting) the edges incident with a vertex in a graph corresponds to removing the elements of a cocircuit in a matroid. In a graph, the edges incident with a vertex are a special type of cocircuit, so the matroid formulation latter is slightly more general even when the matroid is graphic. $\endgroup$ – Gordon Royle Apr 15 '16 at 23:11
  • $\begingroup$ If cocircuit is defined as inclusion-minimal codependent set, then in general set of edges incident with a vertex is not a cocircuit (well, it is always a disjoint union of cocircuits). $\endgroup$ – Fedor Petrov Apr 16 '16 at 7:02
  • $\begingroup$ Also I do not understand why this approach does not prove that $K_6$ is 5-colorable: it has a vertex of degree 5 and all proper minors are 5-colorable. $\endgroup$ – Fedor Petrov Apr 16 '16 at 22:27
  • $\begingroup$ Oxley works with cocircuits, while Woodall/Thomassen each work with sets of edges incident with a vertex. So sometimes Oxley can find a cocircuit strictly smaller than any vertex-star and thereby get a smaller $k$ in the first term. This can make a difference, but only for certain contrived examples. $\endgroup$ – Gordon Royle Apr 17 '16 at 8:17

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.