𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Ramsey linear families and generalized subdivided graphs

✍ Scribed by Yusheng Li; Cecil C. Rousseau; Ľubomír Šoltés

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
342 KB
Volume
170
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V~, 112 ..... Va such that for each i at most d vertices in V~ U... U V, have neighbors in V~+~ and r(Kk, (Vi))<~ pIV(G) I, where (V i) denotes the subgraph of G induced by Vi. Then there exists a number c depending only on p, d, and k such that r(Kk,G)<~c I V(G)t. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I C V(G) such that each component of G-I has at most d vertices and at most two neighbors in I. Then r(G,G)<~cl V(G)[, where c is a number depending only on d. As a special case, r(G,G)<~61V(G) t for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4.

📜 SIMILAR VOLUMES

Subdivided graphs have linear ramsey num
Subdivided graphs have linear ramsey numbers
✍ Noga Alon 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB

## Abstract It is shown that the Ramsey number of any graph with __n__ vertices in which no two vertices of degree at least 3 are adjacent is at most 12__n__. In particular, the above estimate holds for the Ramsey number of any __n__‐vertex subdivision of an arbitrary graph, provided each edge of t

Generalized Split Graphs and Ramsey Numb
Generalized Split Graphs and Ramsey Numbers
✍ András Gyárfás 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 283 KB

A graph G is called a ( p, q)-split graph if its vertex set can be partitioned into A, B so that the order of the largest independent set in A is at most p and the order of the largest complete subgraph in B is at most q. Applying a well-known theorem of Erdo s and Rado for 2-systems, it is shown th

On graphs with linear Ramsey numbers
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
Linear Ramsey numbers of sparse graphs
Linear Ramsey numbers of sparse graphs
✍ Lingsheng Shi 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract The Ramsey number __R__(__G__~1~,__G__~2~) of two graphs __G__~1~ and __G__~2~ is the least integer __p__ so that either a graph __G__ of order __p__ contains a copy of __G__~1~ or its complement __G__^c^ contains a copy of __G__~2~. In 1973, Burr and Erdős offered a total of $25 for se

A note on Ramsey size-linear graphs
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