Polynomial -boundedness conjecture for capped graphs

At least 4 years old · documented by

An ordered graph is a graph equipped with a vertex order. An ordered graph (G,≺)(G,\prec) is capped if, for every four vertices a≺b≺c≺da\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.

References

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.