Ramsey graphs contain many distinct induced subgraphs

DOI10.1007/BF01789457zbMath0728.05044MaRDI QIDQ804596

Noga Alon, Andras Hajnal

Publication date: 1991

Published in: Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

Ramsey graphsmaximum number of vertices in a trivial induced subgraphnumber of isomorphism types of induced subgraphs

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55)

Related Items

SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY, Induced subgraphs of Ramsey graphs with many distinct degrees, Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture, Erdős and Rényi conjecture

Cites Work

• Ramsey-type theorems
• On the number of distinct induced subgraphs of a graph
• Graphs with a small number of distinct induced subgraphs
• Ramsey graphs cannot be defined by real polynomials
• Some remarks on the theory of graphs
• Unnamed Item