Pivot-minor Erdős–Hajnal conjecture

Let HH be a graph. For a graph GG, let α(G)\boldsymbol{\alpha}(G) be its maximum independent-set size and ω(G)\boldsymbol{\omega}(G) its maximum clique size. Pivot-minor Erdős–Hajnal conjecture. For every graph HH, there exists ε>0\varepsilon>0 such that every graph GG with no pivot-minor isomorphic to HH satisfies

max(α(G),ω(G))V(G)ε.\max(\alpha(G),\omega(G))\ge \lvert V(G)\rvert^\varepsilon.

This is the proposed analogue of the Erdős–Hajnal conjecture for pivot-minor containment and is stronger than the corresponding vertex-minor theorem. Its status is not explicitly identified in the supplied passage.

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.