Big line, big clique conjecture for planar visibility graphs
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.
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
Bálint Hujter and Sándor Kisfaludi-Bak, “5 Colorable Visibility Graphs Have Bounded Size or 4 Collinear Points”, arXiv:1410.7273 (2014).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.