The Big-Line-Big-Chromatic-Number Conjecture for planar visibility graphs
The Big-Line-Big-Chromatic-Number Conjecture for planar visibility graphs
Let be a finite set of points in the plane, and let be its visibility graph. A -colouring assigns one of colours to each point. Big-Line-Big-Chromatic-Number Conjecture. For all integers and there is an integer such that if has at least points and is assigned one of colours, then contains collinear points or some visible pair receives the same colour; equivalently, . This weakening follows from the Big-Line-Big-Clique Conjecture and is known for or ; 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
Sign in to submit a solution.
No solutions have been posted yet.