The Erdös-Hajnal Conjecture-A Survey
From MaRDI portal
Publication:2874098
DOI10.1002/jgt.21730zbMath1280.05086arXiv1606.08827OpenAlexW2136450834WikidataQ55969524 ScholiaQ55969524MaRDI QIDQ2874098
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
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
- Tournaments with near-linear transitive subsets
- Excluding paths and antipaths
- Ramsey-type theorems
- The strong perfect graph theorem
- The Erdős-Hajnal conjecture for bull-free graphs
- Density theorems for bipartite graphs and related Ramsey-type results
- A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
- Tournaments and colouring
- Forcing large transitive subtournaments
- On a property of the class of n-colorable graphs
- Upper Bounds for Erdös-Hajnal Coefficients of Tournaments
- Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
- Graph Theory and Probability
- The Ramsey number R(3, t) has order of magnitude t2/log t
- Some remarks on the theory of graphs
- Testing subgraphs in directed graphs
- Ramsey-type theorems with forbidden subgraphs
This page was built for publication: The Erdös-Hajnal Conjecture-A Survey