✦ LIBER ✦

A note on regular Ramsey graphs

✍ Scribed by Noga Alon; Sonny Ben-Shimon; Michael Krivelevich

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 81 KB
Volume: 64
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20453

No coin nor oath required. For personal study only.

✦ Synopsis

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 \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}({{C}}\sqrt{{{n}}\log{{n}}}).\end{document} © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 244–249, 2010

📜 SIMILAR VOLUMES

A Note on Almost Regular Graphs

✍ M. Of Hofmeister Munich 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB

It can easily be seen that a conjecture of RUNGE does not hold for a class of graphs whose members will be called "almost regular". This conjecture is replaced by a weaker one, and a classification of almost regular graphs is given.

A note on Ramsey size-linear graphs

✍ P.N. Balister; R.H. Schelp; M. Simonovits 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB

## Abstract We show that if __G__ is a Ramsey size‐linear graph and __x,y__ ∈ __V__ (__G__) then if we add a sufficiently long path between __x__ and __y__ we obtain a new Ramsey size‐linear graph. As a consequence we show that if __G__ is any graph such that every cycle in __G__ contains at least

A Note on A Family of Directed Strongly

A Note on A Family of Directed Strongly Regular Graphs

✍ Sylvia A. Hobart; T. Justin Shaw 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 54 KB

A note on bipartite subgraphs of triangl

A note on bipartite subgraphs of triangle-free regular graphs

✍ S. C. Locke 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

## Abstract Lower bounds on the size of a maximum bipartite subgraph of a triangle‐free __r__‐regular graph are presented.

On highly ramsey infinite graphs

✍ M. H. Siggers 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract We show that, for __r__ ≥ 2 and __k__ ≥ 3, there exists a positive constant __c__ such that for large enough __n__ there are 2 non‐isomorphic graphs on at most __n__ vertices that are __r__‐ramsey‐minimal for the odd cycle __C__~2__k__+1~. © 2008 Wiley Periodicals, Inc. J Graph Theory 5

A note on Ramsey numbers for books

✍ Vladimir Nikiforov; Cecil C. Rousseau 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 87 KB 👁 1 views

## Abstract The __book with n pages__ __B__~__n__~ is the graph consisting of __n__ triangles sharing an edge. The __book Ramsey number__ __r__(__B__~__m__~,__B__~__n__~) is the smallest integer __r__ such that either __B__~__m__~ ⊂ __G__ or __B__~__n__~ ⊂ __G__ for every graph __G__ of order __r__