Ramsey graphs contain many distinct induced subgraphs

DOI10.1007/BF01789457MaRDI QIDQ804596zbMATHFDO

Authors 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)

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

Cites work

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

Cited in

(15)

• SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
• scientific article; zbMATH DE number 15664 (Why is no real title available?)
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• Induced subgraphs of Ramsey graphs with many distinct degrees
• On the number of distinct induced subgraphs of a graph
• Almost every \(n\)-vertex graph is determined by its \(3 \log_2n\)-vertex subgraphs
• Distinct degrees in induced subgraphs
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• On the number of induced subgraphs of a random graph
• Erdős and Rényi conjecture
• scientific article; zbMATH DE number 786171 (Why is no real title available?)
• Ramsey graphs induce subgraphs of many different sizes
• Graphs with a small number of distinct induced subgraphs
• Small but unwieldy: a lower bound on adjacency labels for small classes
• 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)