Show that every planar graph Gcan be colored using five or fewer colors. (Hint:Use the hint provided for Exercise 40.)
The famous Art Gallery Problem asks how many guards are needed to see all parts of an art gallery, where the gallery is the interior and boundary of a polygon with nsides. To state this problem more precisely, we need some terminology. A point x inside or on the boundary of a simple polygon Pcoversor seesa point yinside or on Pif all points on the line segment xy are in the interior or on the boundary of P. We say that a set of points is a guarding setof a simple polygon Pif for every point yinside Por on the boundary of Pthere is a point xin this guarding set that sees y. Denote by G(P)the minimum number of points needed to guard the simple polygon P. The art gallery problemasks for the function g(n), which is the maximum value of G(P)over all simple polygons with nvertices. That is, g(n)is the minimum positive integer for which it is guaranteed that a simple polygon with nvertices can be guarded with g(n)or fewer guards.
