## Frank Hoffmann Klaus Kriegel Institut für Informatik Freie Universität Berlin Report B 93-08 June 1993

Get the report here or by anonymous ftp: Server: fubinf.inf.fu-berlin.de File: pub/reports/tr-b-93-08.ps.gzWe prove the following graph coloring result: Let

This result implies several new upper bounds for guarding problems including the first non-trivial upper bound for the rectilinear Prison Yard Problem:

1. $[\frac{*n*}{3}]$ vertex guards are sufficient to watch the interior of a rectilinear polygon with holes.

2. $[\frac{5*n*}{12}]+3$ vertex guards resp. $[\frac{*n*+4}{3}]$ point guards are sufficient to watch simultaneously both the interior and exterior of a rectilinear polygon.

Moreover, we show a new lower bound of $[\frac{5*n*}{16}]$ vertex guards for the rectilinear Prison Yard Problem and prove it to be asymptotically tight for the class of othoconvex polygons.