6
$\begingroup$

Is there a simple proof for the 4-color theorem when restricted to (finite) maps all of whose (internal) regions are pentagons? I am in fact most interested in convex pentagons, if that additional structure helps. These maps lead to graphs of maximum degree $\Delta=5$, so a result for such graphs will answer my question.

If all regions are quadrilaterals, then four colors are sometimes necessary, even if all quadrilaterals are convex, e.g.,
convex quads
But here there is a simple proof of 4-colorability: Identify a quadrilateral with an exposed edge, remove it, 4-color the remainder by induction, and replace the quad, coloring it with a color different from its at most three neighbors. Obviously this simple proof fails for pentagons.

Especially the $\Delta=5$ case is likely known to the experts. So a reference would suffice. Thanks!

Improve this question
$\endgroup$
3
  • $\begingroup$ I also think this case seems likely to be known, but sometimes these things can be surprising -- it is not known, for example, whether or not there is a 5-chromatic triangle-free graph of maximum degree 5. $\endgroup$
    – Andrew D. King
    Commented Dec 17, 2010 at 20:12
  • 1
    $\begingroup$ Are you considering the exterior face to be a face or not? I think you are not, because you say that removing an exposed edge leaves another graph all of whose faces are quadrilaterals. But Mark Bennet seems to think you are, when he writes that the only planar graph all of whose faces are pentagons is the dodecahedron. $\endgroup$
    – David E Speyer
    Commented Dec 17, 2010 at 20:41
  • $\begingroup$ @David & Mark: Ah, I see the confusion! Mea cupla! $\endgroup$
    – Joseph O'Rourke
    Commented Dec 17, 2010 at 20:46

2 Answers 2

Reset to default
10
$\begingroup$

If $v$ is a vertex of degree at most 4 in a planar graph $G$ then one can extend a proper 4-coloring of $V(G) \setminus \{v\}$ to $v$ after possibly modifying it using the classical Kempe chain argument. See for example paragraph 5 of the "Summary of proof ideas" section of the Wikipedia entry on the 4-color theorem: http://en.wikipedia.org/wiki/Four_color_theorem

As pentagons with exposed edges correspond to vertices of degree 4 in the dual graph, one can color the map by induction using this trick.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Sergey: This is just what I was seeking! Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Dec 17, 2010 at 20:41
  • $\begingroup$ More generally, all graphs (whether planar or not) of maximal degree 4 are 4-colorable, with the complete graph $K_5$ being the only exception. This is covered by Brooks' Theorem. en.wikipedia.org/wiki/Brooks%27_theorem My only concern with this argument is if we also want to color the external face, and then every vertex in the dual graph has degree >= 5. $\endgroup$
    – Matthew Kahle
    Commented Dec 18, 2010 at 16:09
0
$\begingroup$

So far as I can tell this is not a research question. (Once definitions are carefully done) the only planar map consisting solely of pentagons is the projection of the dodecahedron, which is four colourable. Using Euler's formula, if there are more than 12 pentagons there also has to be a region with more than six sides. Consult a basic text on the four-colour theorem.

Improve this answer
$\endgroup$
6
  • $\begingroup$ @Mark: The region with more than six sides could be the external region. So, one could make a long chain of pentagons glued side-by-side. Of course that would be 2-colorable. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 17, 2010 at 20:40
  • $\begingroup$ Thanks for clarifying that you aren't including the external region. $\endgroup$
    – Mark Bennet
    Commented Dec 17, 2010 at 20:43
  • $\begingroup$ Sorry, my fault, Mark, I didn't see that my figure for quadrilaterals misled! $\endgroup$
    – Joseph O'Rourke
    Commented Dec 17, 2010 at 20:47
  • 1
    $\begingroup$ The only planar graph with all faces pentagonal and all the vertices trivalent is the dodecahedron. I see no reason there couldn't be much larger graphs with all faces pentagonal if you allow some 4-valent vertices. $\endgroup$
    – David E Speyer
    Commented Dec 17, 2010 at 20:51
  • 3
    $\begingroup$ Here is an explicit example: Take $n$ dodecahedra and stack them one on top of another, face to face. So the stack has $10n+2$ pentagonal faces exposed to the outside world, and $2(n-1)$ interior pentagons hidden in the face-to-face joins. Looking at this as a tilings of a single sphere with $10n+2$ pentagons, we see that we can use as many pentagons as we want, at the expense of creating lots of vertices of degree $4$. $\endgroup$
    – David E Speyer
    Commented Dec 17, 2010 at 20:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .