Nes̆etřil's conjecture on the chromatic bound in the GIP theorem

Let FF be a graph with at least one edge. The cited theorem provides a constant c(F)c(F) such that, for every natural number rr, there is a graph GG with χ(G)>r\chi(G)>r, ω(G)=ω(F)\omega(G)=\omega(F), and every induced subgraph of GG without an induced copy of FF having chromatic number at most c(F)c(F). Nes̆etřil's conjecture. Theorem GIP holds with

c(F)=χ(F).c(F)=\chi(F).

The source says this conjecture would give a positive answer to Davies's question, but does not state a resolution.

Sources & referencesView supporting material

Primary source

Christian Reiher, “Graphs of large girth”, arXiv:2403.13571 (2024).

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.