The Erdös-Hajnal Conjecture-A Survey

DOI10.1002/jgt.21730zbMath1280.05086arXiv1606.08827WikidataQ55969524 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

zbMATH Keywords

induced subgraphs; Erdős-Hajnal conjecture

Mathematics Subject Classification ID

05A17: Combinatorial aspects of partitions of integers

05C65: Hypergraphs

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

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

Cites Work