Ramsey graphs contain many distinct induced subgraphs

DOI10.1007/BF01789457zbMATH Open0728.05044MaRDI QIDQ804596FDOQ804596

Authors: Noga Alon, Andras Hajnal 

Publication date: 1991

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

Recommendations

• Sizes of induced subgraphs of Ramsey graphs
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• Ramsey graphs induce subgraphs of quadratically many sizes
• Graphs with a small number of distinct induced subgraphs
• Induced subgraphs of Ramsey graphs with many distinct degrees

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)

Cites Work

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

Cited In (11)

• Title not available (Why is that?)
• On the number of induced subgraphs of a random graph
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• Title not available (Why is that?)
• Induced subgraphs of Ramsey graphs with many distinct degrees
• Small but unwieldy: a lower bound on adjacency labels for small classes
• Erdős and Rényi conjecture
• Graphs with a small number of distinct induced subgraphs
• SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
• On the number of distinct induced subgraphs of a graph
• Isomorphisms between random graphs

This page was built for publication: Ramsey graphs contain many distinct induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804596)