The narrowness conjecture for HH-free graphs

Let GG be a graph. A function f:V(G)[0,1]f:V(G)\to[0,1] is good if, for every perfect induced subgraph PP of GG,

vV(P)f(v)1.\sum_{v\in V(P)} f(v)\leq 1.

For α1\alpha\geq 1, the graph GG is α\alpha-narrow if, for every good function ff,

vV(G)f(v)α1.\sum_{v\in V(G)} f(v)^\alpha\leq 1.

Narrowness conjecture. For every graph HH, there exists a constant α(H)1\alpha(H)\geq 1 such that every HH-free graph GG is α(H)\alpha(H)-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 HH-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

No solutions have been posted yet.