Strong pivot-minor Erdős–Hajnal conjecture

Let HH be a graph. A set of vertices AA is complete to a disjoint set BB if every vertex of AA is adjacent to every vertex of BB, and anti-complete if no such edges exist. Strong pivot-minor Erdős–Hajnal conjecture. For every graph HH, there exists ε>0\varepsilon>0 such that, for every n>1n>1, every nn-vertex graph with no pivot-minor isomorphic to HH has disjoint vertex sets AA and BB satisfying

A,Bεn\lvert A\rvert,\lvert B\rvert\ge \varepsilon n

and AA is complete or anti-complete to BB. This stronger property implies the pivot-minor Erdős–Hajnal conjecture, but the supplied text does not give a general resolution.

Sources & referencesView supporting material

Primary source

Jaehoon Kim and Sang-il Oum, “The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor”, arXiv:2003.12960 (2021).

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.