Reference no: EM131576298

Question: Show that every planar graph G can be colored using five or fewer colors.

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 n sides. To state this problem more precisely, we need some terminology.A point x inside or on the boundary of a simple polygon P covers or sees a point y inside or on P if 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 set of a simple polygon P if for every point y inside P or on the boundary of P there is a point x in 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 problem asks for the function g(n), which is the maximum value of G(P) over all simple polygons with n vertices. That is, g(n) is the minimum positive integer for which it is guaranteed that a simple polygon with n vertices can be guarded with g(n) or fewer guards.