Erdős–Hajnal for graphs with no 5‐hole
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl
Abstract
Abstract The Erdős–Hajnal conjecture says that for every graph there exists such that every graph not containing as an induced subgraph has a clique or stable set of cardinality at least . We prove that this is true when is a cycle of length five. We also prove several further results: for instance, that if is a cycle and is the complement of a forest, there exists such that every graph containing neither of as an induced subgraph has a clique or stable set of cardinality at least .
Topics & Concepts
CombinatoricsMathematicsSplit graphConjectureCardinality (data modeling)Induced subgraphGraphComplement (music)CliqueCographExistential quantificationGraph factorizationBlock graphDistance-hereditary graphDiscrete mathematicsLine graphPathwidthGraph powerComputer scienceChemistryGeneComplementationBiochemistryPhenotypeData miningVertex (graph theory)Limits and Structures in Graph TheoryAdvanced Graph Theory ResearchAdvanced Topology and Set Theory