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.
Welcome to Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange is a question and answer site for
researchers in theoretical computer science and related fields.
It's built and run by you as a part of the Stack Exchange network of Q&A sites. With your help, we're working together to build a library of research-level questions and answers in theoretical computer science.
We're a little bit different from other sites. Here's how:
Ask questions, get answers, no distractions
This site is all about getting answers. It's not a discussion forum. There's no chit-chat.
Just questions...
...and answers.
up vote
Good answers are voted up and rise to the top.
The best answers show up first so that they are always easy to find.
accept
The person who asked can mark one answer as "accepted".
Accepting doesn't mean it's the best answer, it just means that it worked for the person who asked.
Coloring Planar Graphs
up vote
14
down vote
favorite
2 Answers
up vote
4
down vote
accept
Yes, this is a corollary of the Three Color Theorem, see at the bottom here: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html
answered Dec 30 '10 at 18:52
domotorp
3,113831
3,113831
up vote
3
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.
answered Jan 1 '11 at 10:01
Gil Kalai
2,2761336
2,2761336
Tags make it easy to find interesting questions
All questions are tagged with their subject areas. Each can have up to 5 tags, since a question might be related to several subjects.
Click any tag to see a list of questions with that tag, or go to the tag list to browse for topics that interest you.
Coloring Planar Graphs
up vote
14
down vote
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.
asked Dec 30 '10 at 17:19
Lance Fortnow
3,3901130
3,3901130
You earn reputation when people vote on your posts
Your reputation score goes up when others vote up your questions, answers and edits.
+5
question voted up
+10
answer voted up
+15
answer is accepted
+2
edit approved
As you earn reputation, you'll unlock new privileges like the ability to vote, comment, and even edit other people's posts.
| Reputation | Privilege |
|---|---|
| 15 | Vote up |
| 50 | Leave comments |
| 125 | Vote down (costs 1 rep on answers) |
At the highest levels, you'll have access to special moderation tools. You'll be able to work alongside our community moderators to keep the site focused and helpful.
| 2000 | Edit other people's posts |
|---|---|
| 3000 | Vote to close, reopen, or migrate questions |
| 10000 | Access to moderation tools |
Get answers to practical, detailed questions
Focus on questions about an actual problem you have faced. Include details about what you have tried and exactly what you are trying to do.
Ask about...
- Specific research-level questions in theoretical computer science
Not all questions work well in our format. Avoid questions that are primarily opinion-based, or that are likely to generate discussion rather than answers.
Questions that need improvement may be closed until someone fixes them.
Don't ask about...
- Anything not directly related to theoretical computer science
- Questions that are primarily opinion-based
- Questions with too many possible answers or that would require an extremely long answer
- Questions which are not research-level, e.g. exercises in undergraduate textbooks
Improve posts by editing or commenting
Our goal is to have the best answers to every question, so if you see questions or answers that can be improved, you can edit them.
Use edits to fix mistakes, improve formatting, or clarify the meaning of a post.
up vote
9
down vote
Yes, this is a corollary of the Three Color Theorem, see at the bottom here: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html
answered Dec 30 '10 at 18:52
domotorp
3,113831
3,113831
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
Unlock badges for special achievements
Badges are special achievements you earn for participating on the site. They come in three levels: bronze, silver, and gold.
| Student | Asked first question with score of 1 or more |
| Editor | First edit |
| Good Answer | Answer score of 25 or more |
| Civic Duty | Voted 300 or more times |
| Famous Question | Asked a question with 10,000 views |
Find a question to answer, or ask your own
Looking for more in-depth information on the site? Visit the FAQ
Theoretical Computer Science Stack Exchange is part of the Stack Exchange network
Like this site? Stack Exchange is a network of 103 Q&A sites just like it. Check out the full list of sites.
Use comments to ask for more information or clarify a question or answer.
You can always comment on your own questions and answers. Once you earn 50 reputation, you can comment on anybody's post.
Remember: we're all here to learn, so be friendly and helpful!