Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can it always be three colored? Ideally I'd like a small counterexample.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
Yes, this is a corollary of the Three Color Theorem, see at the bottom here: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html
-
1$\begingroup$ Thanks. Do you have a reference for a proof? $\endgroup$ Commented Dec 30, 2010 at 23:29
-
3$\begingroup$ You might look at these two papers: google.com/… and google.com/… $\endgroup$ Commented Dec 31, 2010 at 4:32
-
6$\begingroup$ To add to Malkevitch's references: the equivalence of 3-colorability and even degree for planar triangulations is usually attributed to P. J. Heawood, "On the four-colour map theorem". Quarterly J. Pure Appl. Math. 29:270–285, 1898. However the papers Malkevitch linked have more to say about this attribution. $\endgroup$ Commented Dec 31, 2010 at 5:59
-
6$\begingroup$ Also, the corollary is not mentioned in Hull's notes, only the 3-color theorem itself. But from a 3-connected graph G with triangular internal faces and even internal vertices one can form a maximal planar graph 2G with even vertices simply by stitching two copies of G on the outer face. If G is not 3-connected, one can 3-color its 3-connected components independently. $\endgroup$ Commented Dec 31, 2010 at 6:12
-
1$\begingroup$ The link in the answer didn't go for me but I found it on the wayback machine: https://web.archive.org/web/20100614003714/http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html $\endgroup$ Commented Jan 23 at 19:15
$\begingroup$
$\endgroup$
This result extends to high dimensions. A triangulation of a d-dimensional sphere so that every vertex has an even degree is (d+1) colorable. See, for example this paper: Jacob E. Goodman and Hironori Onishi, Even triangulations of $S^3$ and the coloring of graphs, Trans. Am. Math. Soc. 246 (1978), 501–510.
