Polynomial chromatic-number conjecture for triangle-free intersection graphs of projective lines
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.
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
Sign in to submit a solution.
No solutions have been posted yet.