On the chromatic number of the visibility graph of a set of points in the plane

Jan Kára, Attila Pór, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

25 Citations (Scopus)

Abstract

The visibility graph V(P) of a point set P \subseteq R2 has vertex set P, such that two points v,w P are adjacent whenever there is no other point in P on the line segment between v and w. We study the chromatic number of V(P). We characterise the 2- and 3-chromatic visibility graphs. It is an open problem whether the chromatic number of a visibility graph is bounded by its clique number. Our main result is a super-polynomial lower bound on the chromatic number (in terms of the clique number).
Original languageEnglish
Pages (from-to)497-506
Number of pages10
JournalDiscrete & Computational Geometry
Volume34
Issue number3
DOIs
Publication statusPublished - 2005
Externally publishedYes

Cite this