Polynomial chromatic-number conjecture for high-girth intersection graphs of lines

From papers

Let gNg\in\mathbb{N}. An intersection graph of lines in R3\mathbb{R}^3 has one vertex for each line and edges joining intersecting lines; its girth is the length of its shortest cycle. Polynomial chromatic-number conjecture for high-girth line graphs. For every gNg\in\mathbb{N} there exists ε>0\varepsilon>0 such that, for every sufficiently large nn, there exists an intersection graph of nn lines in R3\mathbb{R}^3 of girth at least gg and chromatic number at least nεn^{\varepsilon}. Davies's result gives arbitrarily large chromatic number at fixed girth, while this conjecture asks for polynomial growth in the number of 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.