Polynomial -boundedness conjecture for capped graphs

An ordered graph is a graph equipped with a vertex order. An ordered graph (G,)(G,\prec) is capped if, for every four vertices abcda\prec b\prec c\prec d, the edges acac and bdbd imply the edge adad. Let ω\omega denote the clique number and χ\chi the chromatic number. Capped-graph polynomial bound conjecture. There is a polynomial function pp such that every capped graph with clique number ω\omega has chromatic number at most p(ω)p(\omega). The paper notes that this would establish polynomial \chi-boundedness for capped graphs and consequently improve the bounds for the related graph classes studied there; it is presented as an expectation rather than a known result.

Sources & referencesView supporting material

Primary source

James Davies, Tomasz Krawczyk, Rose McCarty and Bartosz Walczak, “Colouring polygon visibility graphs and their generalizations”, arXiv:2103.07803 (2021).

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.