Nes̆etřil's conjecture on the chromatic bound in the GIP theorem
Nes̆etřil's conjecture on the chromatic bound in the GIP theorem
Let be a graph with at least one edge. The cited theorem provides a constant such that, for every natural number , there is a graph with , , and every induced subgraph of without an induced copy of having chromatic number at most . Nes̆etřil's conjecture. Theorem GIP holds with
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
Sign in to submit a solution.
No solutions have been posted yet.