A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems

DOI10.1137/S0895480194265611zbMATH Open0852.05049OpenAlexW2071826698MaRDI QIDQ4881287FDOQ4881287

Authors: Frank Hoffmann, Klaus Kriegel 

Publication date: 25 November 1996

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480194265611

Recommendations

• Perfect graphs and guarding rectilinear art galleries
• GUARDING RECTANGULAR PARTITIONS
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
• scientific article; zbMATH DE number 7491438
• On colourability of polygon visibility graphs

zbMATH Keywords

triangulationcolouringvisibilitypolygon-guarding

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cited In (14)

• How to guard orthogonal polygons: diagonal graphs and vertex covers
• Extension to Even Triangulations
• Polychromatic colorings of plane graphs
• Extension to 3-colorable triangulations
• Polychromatic 4-coloring of guillotine subdivisions
• Polychromatic colorings of rectangular partitions
• Euler transformation of polyhedral complexes
• On Some City Guarding Problems
• Facially-constrained colorings of plane graphs: a survey
• New bounds on guarding problems for orthogonal polygons in the plane using vertex guards with halfplane vision
• Polychromatic colorings of bounded degree plane graphs
• Polychromatic 4-coloring of cubic bipartite plane graphs
• Balanced polychromatic 2-coloring of triangulations
• Ortho-unit polygons can be guarded with at most \(\left\lfloor \frac{n-4}{8} \right\rfloor\) guards

This page was built for publication: A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4881287)