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
- 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.