The Erdos-Hajnal conjecture, first posed by Paul Erdos and Andras Hajnal in 1977, states that for any graph H, the family of graphs with no induced subgraph isomorphic to H contains, for every n-vertex member, either a clique or an independent set whose size grows polynomially in n, in contrast to the merely logarithmic guarantee that holds for graphs in general.
Facts
StatementFamilies of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets, of polynomial size in the number of vertices. 1 Proposed Year Progress Toward ResolutionOpen as of 2024; proven for cographs and small graphs, and for the 5-cycle by Chudnovsky, Scott, Seymour and Spirkl. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
Sources
1. Erdos-Hajnal Conjecture (Wikipedia)
Lead section
first posed it as an open problem in a paper from 1977
Lead section [statement] [3]
families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets
Lead section [progress-note]
As of 2024, however, the full conjecture has not been proven, and remains an open problem.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.