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

About 17 years old · traced to

Let PP be a finite set of points in the plane, and let V(P)\mathcal{V}(P) be its visibility graph. A (k−1)(k-1)-colouring assigns one of k−1k-1 colours to each point. Big-Line-Big-Chromatic-Number Conjecture. For all integers k≥2k\geq2 and ℓ≥1\ell\geq1 there is an integer nn such that if PP has at least nn points and is assigned one of k−1k-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 k≤5k\leq5 or ℓ≤3\ell\leq3; the cases beyond these ranges remain open.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.