Towards Erdős-Hajnal for graphs with no 5-hole (Q2288355)

In this paper, all graphs are finite and have no loops or parallel edges. The cardinalities of the largest stable sets and cliques in a graph \(G = (V, E)\) with \(|V|=n\) are denoted by \(\alpha(G)\) and \(\omega(G)\), respectively. For two graphs \(G\) and \(H\) we say that \(G\) contains \(H\) if some induced subgraph of \(G\) is isomorphic to \(H\) and \(G\) is \(H\)-free otherwise. The Erdős-Hajnal conjecture says that for every graph \(H\) there exists \(c > 0\) such that \(\max(\alpha(G), \omega(G)) \geq n^c\) for every \(H\)-free graph \(G\) and this is still open when \(H=C_5\) (\(C_5\) denotes the cycle of length 5). The best general bound for the Erdős-Hajnal conjecture to date \(\max((\alpha(G), \omega(G)) \geq n^{c \sqrt{log(n)}}\) was proved by \textit{P. Erdős} and \textit{A. Hajnal} [Discrete Appl. Math. 25, No. 1--2, 37--52 (1989; Zbl 0715.05052)] for every \(H\)-free graph \(G\) (logarithm is of base 2). This was also the known bound for \(H = C_5\). In this paper, the authors improve the bound to \(\max((\alpha(G), \omega(G)) \geq n^{c \sqrt{log(n) log(n) log(n)}}\) for every \(C_5\)-free graph \(G\).