A note on regular Ramsey graphs

DOI10.1002/JGT.20453MaRDI QIDQ3055921zbMATH OpenOpenAlexFDO

Authors Noga Alon, Sonny Ben-Shimon, Michael Krivelevich

Publication date 10 November 2010

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0812.2386

zbMATH Keywords

Ramsey theoryregular graphs

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55)

Abstract: We prove that there is an absolute constant $C>0$ so that for every natural $n$ there exists a triangle-free emph{regular} graph with no independent set of size at least $Csqrtnlogn$.

Recommendations

• Triangle-free regular graphs
• Independence numbers of locally sparse graphs and a Ramsey type problem
• On the independence number of sparse graphs
• Large independent sets in random regular graphs
• Some Remarks on Ramsay's Theorem

Cites work

• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• On the size of a random maximal graph
• The early evolution of the \(H\)-free process
• The triangle-free process

Cited in

(11)

• The triangle-free process
• Triangle-free regular graphs
• The robust component structure of dense regular graphs and applications
• Sufficient conditions for graphicality of bidegree sequences
• scientific article; zbMATH DE number 26493 (Why is no real title available?)
• An extension of a result of Alon, Ben-Shimon and Krivelevich on bipartite graph vertex sequences
• How (maximally) contextual is quantum mechanics?
• A note on highly connected and well-connected Ramsey theory
• Dynamic concentration of the triangle‐free process
• Solution to a problem of Katona on counting cliques of weighted graphs
• The early evolution of the \(H\)-free process

This page was built for publication: A note on regular Ramsey graphs

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