Big line, big clique conjecture for planar visibility graphs

From papers

Let XX be a finite set of points in the Euclidean plane. For u,vXu,v\in X, let (uv)(uv) denote the open line segment with endpoints uu and vv, and let the visibility graph GXG_X be the graph with vertex set XX in which uu and vv are adjacent exactly when (uv)(uv) contains no point of XX. Big line, big clique conjecture. For any fixed \ell and kk there is a constant c=c(k,)c=c(k,\ell) such that every finite planar point set of size at least cc has either \ell collinear points or a visibility graph with a clique of size kk. This conjecture is currently open for all k6k\geq 6 and 4\ell\geq 4; 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

No solutions have been posted yet.