4-Coloring Of The Art Gallery And A Special Art Gallery For Guarded Guards

The art gallery problem is origin from the real world,and is closely related to thetriangulation of the polygon．For many years,it has attracted more and more researchers．Nowadays,it has very important application in many domains．Because the method of4-coloring for art gallery can reduce the number of guards for most simple polygon,therefore,whether in theory or in the practical application,it is of great significance．On the basis of 3-coloring,the problem of 4-coloring for art gallery and theminimum number of guarded guards in a special kind of simple polygon areinvestigated．Firstly,in art gallery problem for guard,because,the results obtained from themethod of 3-coloring is not optimal for most simple polygon．Therefore,according tothe corresponding relation between the triangulation and the binary tree．By analyzingthe adjacent relation between the two adjacent triangles in the triangulation,using themethod of coloring,the method of 4-coloring and the rules of 4-coloring is proposed,and the problem has been described and analyzed after 4-coloring．Also the condition ofthe every color can cover the whole polygon is obtained,and at least one color cancover the whole polygon is obtained．Then analyze the reason why the points with thesame color can't cover the whole polygon．Secondly,in art gallery problem for guarded guards,Michael established a tightbound for guarded guards:「(3n-1)／7」．In this paper,Based on the analysis of theMichael's prove and the relevant conclusions,first,decomposes the triangulation T_ninto T_n-m+2 and T_m,where m∈{6,7,8,9},and then analyze the triangulation T_m．Finally,by using the inductive method,prove「2n／5」guarded guards always enoughfor a special kind of simple polygon-the triangulation's isomorphic graph iscatenarian．...