Big line, big clique conjecture for planar visibility graphs
Let be a finite set of points in the Euclidean plane. For , let denote the open line segment with endpoints and , and let the visibility graph be the graph with vertex set in which and are adjacent exactly when contains no point of . Big line, big clique conjecture. For any fixed and there is a constant such that every finite planar point set of size at least has either collinear points or a visibility graph with a clique of size . This conjecture is currently open for all and ; finiteness is necessary because infinite point sets provide counterexamples.
References
Primary source
Bálint Hujter and Sándor Kisfaludi-Bak, “5 Colorable Visibility Graphs Have Bounded Size or 4 Collinear Points”, arXiv:1410.7273 (2014).
Progress summary
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.