Coloring polygon visibility graphs and their generalizations

DOI10.1016/J.JCTB.2023.02.010MaRDI QIDQ6038590zbMATH OpenFDO

Authors James E. Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak

Publication date 2 May 2023

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2103.07803

zbMATH Keywords

\( \chi \)-boundednessordered graphspseudoline arrangementsvisibility graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10)

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 $omega$ has chromatic number at most $3cdot{4}^{omega-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.

Recommendations

• On colourability of polygon visibility graphs
• On the chromatic number of the visibility graph of a set of points in the plane
• A characterization of visibility graphs for pseudo-polygons

Cites work

• A linear time algorithm for minimum link paths inside a simple polygon
• A note on visibility graphs
• Chromatic number of ordered graphs with forbidden ordered subgraphs
• Coloring curves that cross a fixed curve
• Computing the maximum clique in the visibility graph of a simple polygon
• Extending drawings of graphs to arrangements of pseudolines
• Graph Drawing
• scientific article; zbMATH DE number 1759472 (Why is no real title available?)
• Improved bounds for the conflict-free chromatic art gallery problem
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Induced subgraphs of graphs with large chromatic number. VI. Banana trees
• Max point-tolerance graphs
• Non-stretchable pseudo-visibility graphs
• On a Coloring Problem.
• On characterizing terrain visibility graphs
• On colourability of polygon visibility graphs
• On conflict-free chromatic guarding of simple polygons
• On recognizing and characterizing visibility graphs of simple polygons
• On the chromatic number of disjointness graphs of curves
• On the chromatic number of multiple interval graphs and overlap graphs
• On the chromatic number of the visibility graph of a set of points in the plane
• Outerstring graphs are -bounded
• Recognition and complexity of point visibility graphs
• Triangle-free intersection graphs of line segments with large chromatic number
• Unsolved problems in visibility graphs of points, segments, and polygons
• Visibility graphs and oriented matroids
• Visibility graphs of point sets in the plane
• Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains

Cited in

(8)

• Helly-type theorems for appropriate colorings of visibility sets
• Coloring Delaunay-edges and their generalizations
• On the chromatic number of the visibility graph of a set of points in the plane
• On colourability of polygon visibility graphs
• On colourability of polygon visibility graphs
• A survey of degree-boundedness
• Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
• Compact representation of semilinear and terrain-like graphs

This page was built for publication: Coloring polygon visibility graphs and their generalizations

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