Post #506

New Proof Reveals That Graphs With No Pentagons Are Fundamentally Different A new article at Quanta about Erdős–Hajnal conjecture, which states that any graph that forbids having some small subgraph will inevitably have a large clique or a large independent set. The article talks about a recent paper that confirms the conjecture for a special case which was deemed the hardest. Now there is a hope that the conjecture is true for the general case.