The narrowness conjecture for -free graphs
The narrowness conjecture for -free graphs
Let be a graph. A function is good if, for every perfect induced subgraph of ,
For , the graph is -narrow if, for every good function ,
Narrowness conjecture. For every graph , there exists a constant such that every -free graph is -narrow.
Fox showed that this conjecture is equivalent to the Erdős–Hajnal conjecture. It is known for some classes, including bull-free graphs, but remains open for general -free graphs.
Sources & referencesView supporting material
Primary source
Maria Chudnovsky, “The Erdös-Hajnal Conjecture—A Survey”, arXiv:1606.08827 (2016).
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.