Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 17 down vote favorite
2

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.

share|improve this question

2 Answers

up vote 22 down vote accepted

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

share|improve this answer
1  
Thanks. Do you have a reference for a proof? – Lance Fortnow Dec 30 '10 at 23:29
3  
You might look at these two papers: google.com/… and google.com/… – Joseph Malkevitch Dec 31 '10 at 4:32
4  
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. – David Eppstein Dec 31 '10 at 5:59
5  
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. – David Eppstein Dec 31 '10 at 6:12
up vote 22 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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