21
$\begingroup$

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.

$\endgroup$
25
$\begingroup$

Yes, this is a corollary of the Three Color Theorem, see at the bottom here: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html

$\endgroup$
  • 1
    $\begingroup$ Thanks. Do you have a reference for a proof? $\endgroup$ – Lance Fortnow Dec 30 '10 at 23:29
  • 3
    $\begingroup$ You might look at these two papers: google.com/… and google.com/… $\endgroup$ – Joseph Malkevitch Dec 31 '10 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$ – David Eppstein Dec 31 '10 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$ – David Eppstein Dec 31 '10 at 6:12
24
$\begingroup$

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.

$\endgroup$

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.