Polynomial χ-boundedness of grounded segment graphs
Polynomial χ-boundedness of grounded segment graphs
A grounded segment graph is the intersection graph of a collection of line segments grounded on a common line. Grounded segment-graph conjecture. The class of grounded segment graphs is polynomially χ-bounded. Grounded segment graphs are a class of geometric intersection graphs; the conjecture asks whether their chromatic number is bounded by a polynomial in their clique number, extending the polynomial χ-boundedness results discussed for related grounded classes. The source presents this as an open question and gives no resolution.
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
James Davies, Tomasz Krawczyk, Rose McCarty and Bartosz Walczak, “Grounded L-graphs are polynomially χ-bounded”, arXiv:2108.05611 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.