Polynomial chromatic-number conjecture for high-girth intersection graphs of lines
Let . An intersection graph of lines in 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 there exists such that, for every sufficiently large , there exists an intersection graph of lines in of girth at least and chromatic number at least . Davies's result gives arbitrarily large chromatic number at fixed girth, while this conjecture asks for polynomial growth in the number of 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.