Polynomial -boundedness conjecture for capped graphs
Polynomial -boundedness conjecture for capped graphs
An ordered graph is a graph equipped with a vertex order. An ordered graph is capped if, for every four vertices , the edges and imply the edge . Let denote the clique number and the chromatic number. Capped-graph polynomial bound conjecture. There is a polynomial function such that every capped graph with clique number has chromatic number at most . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.