1
$\begingroup$

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

  • 0
    Also posted to MathOverflow.2012-01-27

2 Answers 2

3

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.

  • 0
    I'm not only looking for great historical problems but it will be good too.2012-01-27
2

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!