Art galleries as described in the article (as triangulations of polygons with some interior lines missing, the interior lines being added as part of the proof) are outerplanar. An earlier proof that the chromatic number of an outerplanar graph is at most three -- and that a triangulation of a polygon not only has chromatic number three but that there is only one way (except for interchange of color names) to achieve such a coloring -- was given by Chartrand and Geller, and appears as an exercise in Frank Harary's textbook (page 149).
Add new comment
Teo tells us about his work in artificial intelligence, his travels around the world, and how inspiration sometimes strikes in the pub.
Clouds make the weather, yet their detail isn't taken into account in weather forecasts. Artificial intelligence might be able to help.
Predicting the weather is hard. But with more data and computing power becoming available, artificial intelligence may be able to help.
How does your phone know what the weather's going to be like?
How a little insect can cause chaos.