A note on regular ramsey graphs

Noga Alon; Sonny Ben-Shimon; Michael Krivelevich

doi:10.1002/jgt.20453

A note on regular ramsey graphs

Noga Alon, Sonny Ben-Shimon, Michael Krivelevich

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

We prove that there is an absolute constant C>0 so that for every natural n there exists a triangle-free regular graph with no independent set of size at least C√nlog n.

Original language	English (US)
Pages (from-to)	244-249
Number of pages	6
Journal	Journal of Graph Theory
Volume	64
Issue number	3
DOIs	https://doi.org/10.1002/jgt.20453
State	Published - Jul 2010
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Ramsey theory
Regular graphs

Access to Document

10.1002/jgt.20453

Cite this

@article{c3814fcf2ec44049a6e7bef94a0cbc4c,

title = "A note on regular ramsey graphs",

abstract = "We prove that there is an absolute constant C>0 so that for every natural n there exists a triangle-free regular graph with no independent set of size at least C√nlog n.",

keywords = "Ramsey theory, Regular graphs",

author = "Noga Alon and Sonny Ben-Shimon and Michael Krivelevich",

year = "2010",

month = jul,

doi = "10.1002/jgt.20453",

language = "English (US)",

volume = "64",

pages = "244--249",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - A note on regular ramsey graphs

AU - Alon, Noga

AU - Ben-Shimon, Sonny

AU - Krivelevich, Michael

PY - 2010/7

Y1 - 2010/7

N2 - We prove that there is an absolute constant C>0 so that for every natural n there exists a triangle-free regular graph with no independent set of size at least C√nlog n.

AB - We prove that there is an absolute constant C>0 so that for every natural n there exists a triangle-free regular graph with no independent set of size at least C√nlog n.

KW - Ramsey theory

KW - Regular graphs

UR - http://www.scopus.com/inward/record.url?scp=77954340720&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954340720&partnerID=8YFLogxK

U2 - 10.1002/jgt.20453

DO - 10.1002/jgt.20453

M3 - Article

AN - SCOPUS:77954340720

SN - 0364-9024

VL - 64

SP - 244

EP - 249

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

A note on regular ramsey graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this