Colouring polygon visibility graphs and their generalizations

2021/03/13 by Davies, James, Krawczyk, Tomasz, McCarty, Rose +1 · 1 citation
#05C15 #05C62 #52C30 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2103.07803

Abstract

Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with clique number ω has chromatic number at most 3⋅ 4^ω-1. The proof is carried through in the setting of ordered graphs; we identify two conditions satisfied by every curve pseudo-visibility graph (considered as an ordered graph) and prove that they are sufficient for the claimed bound. The proof is algorithmic: both the clique number and a colouring with the claimed number of colours can be computed in polynomial time.

Cited by

• A simple layered-wheel-like construction

Related

• On Colourability of Polygon Visibility Graphs
• A Characterization of Visibility Graphs for Pseudo-Polygons
• On colouring point visibility graphs
• Pseudo-Triangle Visibility Graph: Characterization and Reconstruction
• 5 Colorable Visibility Graphs Have Bounded Size or 4 Collinear Points