Visibility Graphs of Points, Segments and Polygons — Conjecture 6

Definitions and mathematical statement

The supplied record does not define a $k$-blocked point set. The following is a conditional formalization using finite planar point visibility and exactly $k$ nonempty colour classes; these conventions require confirmation against the source.

Let $k\in{\mathbb{Z}}_{\geq 1}$ and let $P\subset{\mathbb{R}}^2$ be finite. For distinct $p,q\in P$, define the open segment \[ (p,q)=\{(1-t)p+tq:0<t<1\}. \] The points $p$ and $q$ are visible with respect to $P$ if $(p,q)\cap P=\varnothing$. In the interpretation used here, a $k$-blocked colouring is a surjective map $c:P\to\{1,\ldots,k\}$ satisfying \[ \forall p,q\in P,\quad p\ne q\ \Longrightarrow\ \left((p,q)\cap P=\varnothing\ \Longleftrightarrow\ c(p)\ne c(q)\right). \] Thus points of different colours are visible, and every pair of distinct points of the same colour has a point of $P$ in its open connecting segment. No general-position assumption is imposed.

Conjecture 6 (as recorded, under this interpretation). For every $k\in{\mathbb{Z}}_{\geq 1}$, every finite $P\subset{\mathbb{R}}^2$, and every $k$-blocked colouring $c$ of $P$, \[ \forall i\in\{1,\ldots,k\},\qquad |c^{-1}(\{i\})|\leq k. \] The source record labels this conjecture open; that label is supplied registry information, not an independently verified mathematical or literature assessment.

Short English statement

Under the stated interpretation of $k$-blocked, a finite planar point set has exactly $k$ colours, and two distinct points see each other precisely when their colours differ. The conjecture says that each colour occurs on at most $k$ points. The definition of $k$-blocked is absent from the supplied extract and requires source confirmation.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $800536$, source problem code catalogue entry, title Visibility Graphs of Points, Segments and Polygons --- Conjecture 6. The registry records Ghosh and Goswami as proposers, the year $2010$, and status open.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Conjecture 6. Supplied source URL: https://arxiv.org/abs/1012.5187. The supplied background records access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance statements, not claims of independent access or verification here.