The Big-Line-Big-Chromatic-Number Conjecture for planar visibility graphs

From papers

Let PP be a finite set of points in the plane, and let V(P)\mathcal{V}(P) be its visibility graph. A (k1)(k-1)-colouring assigns one of k1k-1 colours to each point. Big-Line-Big-Chromatic-Number Conjecture. For all integers k2k\geq2 and 1\ell\geq1 there is an integer nn such that if PP has at least nn points and is assigned one of k1k-1 colours, then PP contains \ell collinear points or some visible pair receives the same colour; equivalently, χ(V(P))k\chi(\mathcal{V}(P))\geq k. This weakening follows from the Big-Line-Big-Clique Conjecture and is known for k5k\leq5 or 3\ell\leq3; the cases beyond these ranges remain open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Attila Pór and David R. Wood, “On Visibility and Blockers”, arXiv:0912.1150 (2009).

Solutions 0

No solutions have been posted yet.