27 problems

Erdős–Hajnal conjecture. Every proper hereditary class of graphs has the Erdős–Hajnal property.

Directed Erdős–Hajnal conjecture. For every tournament $H$, there exists $epsilon(H)>0$ such that every $H$-free tournament with $n$ vertices contains a transitive subtournament of…

Multicolor Erdős–Hajnal conjecture. There exists $\varepsilon>0$ such that every coloring of the edges of $K_n$ contains either $k$ vertices whose edges are colored according to…

Linear-dimension strengthening. The multicoloured geometric Erdős–Hajnal conjecture and the geometric Erdős–Hajnal conjecture for induced restrictions should both hold with…

Geometric Erdős–Hajnal conjecture. For every prime power $q$ and all $k\in\mathbb N$ and $H\subseteq\operatorname{PG}(k-1,q)$, there exist $\delta,C>0$ such that, for all…

Multicoloured geometric Erdős–Hajnal conjecture. For every prime power $q$, all $k,s_0,s\in\mathbb N$ with $s_0\le s$, and every $s_0$-colouring $c_0$ of $\operatorname{PG}(k-1,q)$…

Multicoloured Erdős–Hajnal conjecture. For all $1\le s_0\le s$ and $k\ge1$, and every $s_0$-colouring $c_0$ of $K_k$, there exist $\delta,C>0$ such that, for all $n\in\mathbb N$ an…

Arnold–Gowers–Sudakov conjecture. Every non-empty $Q$ and every $Q$-free $cell$-graph on $n$ vertices contains a homogeneous set of size at least

Let $H$ be a tournament. An $H$-free tournament is one that does not contain $H$ as a not necessarily induced subdigraph. For a tournament $T$, write $\vec\alpha(T)$ for its maximu…

Let $H$ be a graph, and let $G$ be an $n$-vertex graph containing no induced copy of $H$. The lopsided Erdős–Hajnal conjecture. There exists a constant $c=c(H)>0$ such that $G$ con…

Size-version of the Erdős–Hajnal conjecture. There is a positive constant $\epsilon$ such that every colouring $c$ of $K_n$ in colours from $[s]$ avoiding $T$ satisfies

Alon–Pach–Solymosi conjecture. For every ordered graph $(H,<')$ there exists $\tau>0$ such that

Fox–Sudakov conjecture. For every graph $H$ and every $x>0$, there exists $\delta>0$, polynomial in $x$, such that every $H$-free graph $G$ has a set $S\subseteq V(G)$ with…

Forest characterization conjecture. If a tournament $H$ has an ordering of its vertices for which the backward arc digraph is a forest, then $H$ has the strong Erdős–Hajnal propert…

Let $H$ be a graph. For a graph $G$, let $\boldsymbol{\alpha}(G)$ be its maximum independent-set size and $\boldsymbol{\omega}(G)$ its maximum clique size. Pivot-minor Erdős–Hajnal…

Alon–Pach–Solymosi conjecture. For every tournament $S$ there exists $\varepsilon>0$ such that every $S$-free $n$-vertex tournament contains a transitive subtournament on at least…

An ideal has the strong Erdős–Hajnal property if some $ε>0$ guarantees that every graph $G$ in the ideal with more than one vertex has disjoint sets $A,B e ewcommand{chi}{χ}$ with…

Conlon–Sudakov–Scott saturation bounded sparse-pair conjecture. For every graph $H$ there exist $\varepsilon,s>0$ such that for every $\varepsilon$-bounded graph $G$ on $n$ vertice…

Conlon–Sudakov–Scott bounded sparse-pair conjecture. For every graph $H$ there exist $\varepsilon,s>0$ such that for every $H$-free $\varepsilon$-bounded graph $G$ on $n>1$ vertice…

Conlon–Sudakov–Scott density-pair conjecture. For every graph $H$ there exist $\varepsilon,s>0$ such that for every $H$-free graph $G$ on $n>1$ vertices and every $c$ with…

Conlon–Sudakov–Scott conjecture. For every graph $H$ there exists $\varepsilon>0$ such that every $H$-free graph $G$ with $n>1$ vertices contains a complete or anticomplete…

Forest–complement forest pure-pair conjecture. For every forest $H$, there exists $\varepsilon>0$ such that for every graph $G$ with $|G|>1$ that is both $H$-free and…

Bipartite forest conjecture. For every forest $T$ there exists $\epsilon>0$ such that either some vertex of $G$ has degree at least $\epsilon n$, or there are anticomplete sets…

Sparse Erdős–Hajnal conjecture. For every proper ideal $\mathcal I$ there exist $\epsilon>0$ and $c>0$ such that every $\epsilon$-coherent graph $G\in\mathcal I$ satisfies

Polynomial Rödl dependence conjecture. The dependence of $\delta$ on $d$ can be chosen polynomial; that is, there are constants $C>0$ and $k>0$ such that one may take…