Ramsey graphs contain many distinct induced subgraphs

DOI10.1007/BF01789457MaRDI QIDQ804596zbMATH OpenFDO

Authors Noga Alon, Andras Hajnal

Publication date 1991

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

Full work available at URL https://doi.org/10.1007/BF01789457

zbMATH Keywords

maximum number of vertices in a trivial induced subgraphnumber of isomorphism types of induced subgraphsRamsey graphs

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)

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

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)