Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm a high school student and writing a paper about graph coloring. Can you tell me something about some interesting problems in graph theory connected with graph coloring? Such as full triangle coloring or 2COL problem? i will be pleased. :)

Sorry for my bad english, John

share|cite|improve this question
There are of course generalizations of chromatic polynomials. I believe there is even some game-theoretic research of coloring which you could google for. Also helpful would be to look through anything related to Bill Tutte. – anon Jan 27 '12 at 20:40
Also posted to MathOverflow. – Gerry Myerson Jan 27 '12 at 22:19

I think historically one of the problems that have drawn most attention in the context you are asking is the Four Color Problem. Look up Four Color Theorem on Wikipedia and you'll find tuns of information on it.

share|cite|improve this answer
I'm not only looking for great historical problems but it will be good too. – John Jan 27 '12 at 20:59

Consider the graph whose vertex set is every point in the real plane. We will say two vertices in this graph are adjacent whenever they are exactly unit distance apart. For example, the points $(0, 0)$ and $(\sqrt{2}/2, \sqrt{2}/2)$ are adjacent in this graph.

The Hadwiger-Nelson Problem asks for the chromatic number of the graph defined above. It turns out it is not too hard to show the chromatic number at least 4 and no more than 7 (the Wikipedia article discusses these bounds), but it gets very strange to go much further. For example, it has been shown the answer may vary depending on which model of set theory you work in!

share|cite|improve this answer

Your Answer


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.