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

About 3 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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.