Polynomial chromatic-number conjecture for triangle-free intersection graphs of projective lines
An intersection graph of lines in has one vertex for each projective line and edges joining intersecting lines; it is triangle-free when it has no -cycle. Polynomial chromatic-number conjecture for projective line graphs. There exists such that, for every sufficiently large , there exists a triangle-free intersection graph of lines in of chromatic number at least . Triangle-free projective-line intersection graphs of arbitrarily large chromatic number are known, but the asserted polynomial dependence on 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
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.