The Erdös-Hajnal Conjecture-A Survey

DOI10.1002/jgt.21730zbMath1280.05086arXiv1606.08827OpenAlexW2136450834WikidataQ55969524 ScholiaQ55969524MaRDI QIDQ2874098

Maria Chudnovsky

Publication date: 28 January 2014

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.08827

zbMATH Keywords

induced subgraphs Erdős-Hajnal conjecture

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Hypergraphs (05C65) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (46)

Clique-stable set separation in perfect graphs with no balanced skew-partitions ⋮ A characterization of claw-free CIS graphs and new results on the order of CIS graphs ⋮ Linear-sized independent sets in random cographs and increasing subsequences in separable permutations ⋮ Triangle-free graphs with no six-vertex induced path ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor ⋮ Excluding hooks and their complements ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Unavoidable Subtournaments in Large Tournaments with No Homogeneous Sets ⋮ On 3‐graphs with no four vertices spanning exactly two edges ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs ⋮ On graphs with no induced five‐vertex path or paraglider ⋮ Caterpillars in Erdős-Hajnal ⋮ Unavoidable tournaments ⋮ A note on the Erdős-Hajnal property for stable graphs ⋮ A further extension of Rödl's theorem ⋮ Unnamed Item ⋮ String graphs have the Erdős-Hajnal property ⋮ Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons ⋮ On Betti numbers of flag complexes with forbidden induced subgraphs ⋮ DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Two Erdős-Hajnal-type theorems in hypergraphs ⋮ Packing edge-disjoint triangles in regular and almost regular tournaments ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ RAMSEY GROWTH IN SOME NIP STRUCTURES ⋮ Erdős-Hajnal-type results for monotone paths ⋮ Induced Turán Numbers ⋮ The Erdős-Hajnal conjecture for rainbow triangles ⋮ Coloring dense digraphs ⋮ On low rank-width colorings ⋮ On the chromatic number of (P_{5},windmill)-free graphs ⋮ Pure pairs. II: Excluding all subdivisions of a graph ⋮ Strong cliques in diamond-free graphs ⋮ The Erdös--Hajnal Conjecture for Long Holes and Antiholes ⋮ Coloring tournaments: from local to global ⋮ Metrically homogeneous graphs of diameter 3 ⋮ Ordered graphs and large bi-cliques in intersection graphs of curves ⋮ Bipartite Independence Number in Graphs with Bounded Maximum Degree ⋮ Large Homogeneous Submatrices ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ The Erdős-Hajnal conjecture for paths and antipaths ⋮ The Erdős-Hajnal conjecture for three colors and triangles

Cites Work

This page was built for publication: The Erdös-Hajnal Conjecture-A Survey