Polynomial chromatic-number conjecture for high-girth intersection graphs of lines
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.
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.