Visibility Graphs of Points, Segments and Polygons — Problem 25

Definitions and mathematical statement

Let $\mathcal B_k$ denote the class of bar $k$-visibility graphs intended by the cited source. The supplied excerpt does not define this class: the permitted bar configurations, the precise visibility rule, the treatment of intersections at endpoints, and whether visibility requires positive width remain to be checked. Consequently, the statements below are conditional on recovering that definition; no particular geometric convention is imposed here.

For a graph $G=(V,E)$, write $\deg_G(v)$ for the degree of $v$. For a nonnegative integer $d$, the graph is $d$-regular if $\deg_G(v)=d$ for every $v\in V$. Its chromatic number $\chi(G)$ is the least number of colors in a vertex coloring assigning different colors to adjacent vertices. Define the existence assertion \[ \mathsf{Exist}(k,d):\quad \text{there exists }G\in\mathcal B_k\text{ with }V(G)\ne\varnothing\text{ and }\deg_G(v)=d\text{ for every }v\in V(G). \] Nonemptiness is an explicit interpretation of the existence questions, to avoid a vacuous empty-graph example. The supplied excerpt does not specify whether graphs must be finite.

The source poses three tasks:

1. Determine whether $\mathsf{Exist}(k,2k+2)$ holds for $k\geq5$. The parameter $k$ is integral. The wording does not explicitly distinguish existence for every such $k$ from existence for at least one such $k$; these are different assertions.
2. Determine whether $\mathsf{Exist}(k,d)$ holds with \[ d\geq2k+3. \] The supplied sentence does not specify the range of $k$, whether the preceding restriction $k\geq5$ continues to apply, or whether existence is requested for some or all eligible parameter pairs.
3. Improve the upper bound reported by the source, \[ \chi(G)\leq6k+6\qquad(G\in\mathcal B_k). \] A strict improvement at a parameter $k$ would give a bound $U(k)<6k+6$ such that $\chi(G)\leq U(k)$ for every $G\in\mathcal B_k$. The excerpt does not specify the parameter range over which an improvement is required. The displayed existing bound is a supplied source claim, not an independently verified theorem or a claim about the present literature.

Short English statement

Problem 25 asks about the existence of regular bar $k$-visibility graphs of degrees $2k+2$ and at least $2k+3$, and asks for an improvement to the reported chromatic bound $6k+6$. The geometric definition and several parameter quantifiers are missing from the supplied excerpt. The registry labels the problem open; this draft does not independently verify that status.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $800551$, exact source code catalogue entry, title "Visibility Graphs of Points, Segments and Polygons --- Problem 25." The registry attributes the problem to Ghosh and Goswami, with proposed year 2010, and supplies status open. Upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 25: https://arxiv.org/abs/1012.5187. This reference and attribution are supplied by the record; the referenced document was not independently consulted for this draft.
• Supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. This date describes supplied source-access metadata, not independent verification of the formulation, the reported bound, or current problem status. No separate literature-verification assessment is supplied.