On colourability of polygon visibility graphs

DOI10.1016/J.EJC.2023.103820MaRDI QIDQ6181985zbMATH OpenOpenAlexFDO

Authors 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) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies for image processing (68U10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On colourability of polygon visibility graphs
• Coloring polygon visibility graphs and their generalizations
• scientific article; zbMATH DE number 4085050

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A game of cops and robbers
• An optimal visibility graph algorithm for triangulated simple polygons
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
• Computational complexity of art gallery problems
• Computing the maximum clique in the visibility graph of a simple polygon
• Hiding people in polygons
• Improved bounds for the conflict-free chromatic art gallery problem
• On \(k\)-visibility graphs
• On colourability of polygon visibility graphs
• On the chromatic number of the visibility graph of a set of points in the plane
• Some NP-hard polygon decomposition problems
• Systolic algorithms for computing the visibility polygon and triangulation of a polygonal region
• The vertex-edge visibility graph of a polygon
• Tight bounds for conflict-free chromatic guarding of orthogonal art galleries
• 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

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