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

DOI10.1137/S0895480194265611MaRDI QIDQ4881287zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

triangulationcolouringvisibilitypolygon-guarding

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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

Cited in

(14)

• Polychromatic colorings of bounded degree plane graphs
• Balanced polychromatic 2-coloring of triangulations
• New bounds on guarding problems for orthogonal polygons in the plane using vertex guards with halfplane vision
• Extension to 3-colorable triangulations
• Facially-constrained colorings of plane graphs: a survey
• Extension to Even Triangulations
• Polychromatic 4-coloring of guillotine subdivisions
• Euler transformation of polyhedral complexes
• Polychromatic 4-coloring of cubic bipartite plane graphs
• Polychromatic colorings of rectangular partitions
• Polychromatic colorings of plane graphs
• How to guard orthogonal polygons: diagonal graphs and vertex covers
• On Some City Guarding Problems
• 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)