✦ LIBER ✦

A note on Ramsey size-linear graphs

✍ Scribed by P.N. Balister; R.H. Schelp; M. Simonovits

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 96 KB
Volume: 39
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10001

No coin nor oath required. For personal study only.

✦ Synopsis

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 four consecutive vertices of degree 2 then G is Ramsey size‐linear. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 1–5, 2002

📜 SIMILAR VOLUMES

A note on regular Ramsey graphs

✍ Noga Alon; Sonny Ben-Shimon; Michael Krivelevich 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 81 KB

## 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

On graphs with linear Ramsey numbers

✍ R. L. Graham; V. Rödl; A. Ruciński 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB 👁 1 views

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__

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th

On graphs with small Ramsey numbers

✍ A. V. Kostochka; V. Rödl 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB

## Abstract Let __R__(__G__) denote the minimum integer __N__ such that for every bicoloring of the edges of __K~N~__, at least one of the monochromatic subgraphs contains __G__ as a subgraph. We show that for every positive integer __d__ and each γ,0 < γ < 1, there exists __k__ = __k__(__d__,γ) su