On colourability of polygon visibility graphs

DOI10.1016/j.ejc.2023.103820OpenAlexW2949783980MaRDI QIDQ6181985

Onur Çağırıcı, Petr Hliněný, Bodhayan Roy

Publication date: 23 January 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2023.103820

zbMATH Keywords

polynomial algorithm for 4-colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A game of cops and robbers
• Systolic algorithms for computing the visibility polygon and triangulation of a polygonal region
• An optimal visibility graph algorithm for triangulated simple polygons
• Hiding people in polygons
• The vertex-edge visibility graph of a polygon
• On colouring point visibility graphs
• Computing the maximum clique in the visibility graph of a simple polygon
• On the chromatic number of the visibility graph of a set of points in the plane
• On k-visibility graphs
• Computational complexity of art gallery problems
• Some NP-hard polygon decomposition problems
• Improved bounds for the conflict-free chromatic art gallery problem
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
• On Colourability of Polygon Visibility Graphs
• Visibility Algorithms in the Plane
• Visibility graphs of point sets in the plane

This page was built for publication: On colourability of polygon visibility graphs