Towards the Erdős-Hajnal conjecture for P5 -free graphs

Pablo Blanco, Matija Bucić

Research output: Contribution to journalArticlepeer-review


The Erdős-Hajnal conjecture is one of the most classical and well-known problems in extremal and structural combinatorics dating back to 1977. It asserts that in stark contrast to the case of a general n-vertex graph, if one imposes even a little bit of structure on the graph, namely by forbidding a fixed graph H as an induced subgraph, instead of only being able to find a polylogarithmic size clique or an independent set, one can find one of polynomial size. Despite being the focus of considerable attention over the years, the conjecture remains open. In this paper, we improve the best known lower bound of 2Ω(logn) on this question, due to Erdős and Hajnal from 1989, in the smallest open case, namely when one forbids a P5 , the path on 5 vertices. Namely, we show that any P5 -free n-vertex graph contains a clique or an independent set of size at least 2Ω(logn)2/3 . We obtain the same improvement for an infinite family of graphs.

Original languageEnglish (US)
Article number2
JournalResearch in Mathematical Sciences
Issue number1
StatePublished - Mar 2024

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics (miscellaneous)
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Towards the Erdős-Hajnal conjecture for P5 -free graphs'. Together they form a unique fingerprint.

Cite this