Davies, James
[VerfasserIn];
Krawczyk, Tomasz
[VerfasserIn];
McCarty, Rose
[VerfasserIn];
Walczak, Bartosz
[VerfasserIn]
;
James Davies and Tomasz Krawczyk and Rose McCarty and Bartosz Walczak
[MitwirkendeR]
Colouring Polygon Visibility Graphs and Their Generalizations
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.