Polynomial chromatic-number conjecture for triangle-free intersection graphs of projective lines

From papers

An intersection graph of lines in PR3\mathbb{PR}^3 has one vertex for each projective line and edges joining intersecting lines; it is triangle-free when it has no 33-cycle. Polynomial chromatic-number conjecture for projective line graphs. There exists ε>0\varepsilon>0 such that, for every sufficiently large nn, there exists a triangle-free intersection graph of nn lines in PR3\mathbb{PR}^3 of chromatic number at least nεn^{\varepsilon}. Triangle-free projective-line intersection graphs of arbitrarily large chromatic number are known, but the asserted polynomial dependence on nn remains open; the source notes that affine constructions rely on parallel lines.

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

István Tomon, “Coloring lines and Delaunay graphs with respect to boxes”, arXiv:2301.10129 (2023).

Solutions 0

No solutions have been posted yet.