# Graph Coloring - searching for some interesting problems

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

-
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.

-
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!

-