✦ LIBER ✦

Subdivided graphs have linear ramsey numbers

✍ Scribed by Noga Alon

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 247 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180406

No coin nor oath required. For personal study only.

✦ Synopsis

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 the original graph is subdivided at least once. This settles a problem of Burr and Erdös.

📜 SIMILAR VOLUMES

Anti-Ramsey Numbers of Subdivided Graphs

✍ Tao Jiang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 88 KB

Given a positive integer n and a family F of graphs, the anti-Ramsey number f(n, F) is the maximum number of colors in an edge-coloring of K n such that no subgraph of K n belonging to F has distinct colors on its edges. The Tura ´n number ex(n, F) is the maximum number of edges of an n-vertex graph

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

✍ 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

Irredundant ramsey numbers for graphs

✍ R. C. Brewster; E. J. Cockayne; C. M. Mynhardt 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 356 KB

Constrained Ramsey numbers of graphs

✍ Robert E. Jamison; Tao Jiang; Alan C. H. Ling 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract Given two graphs __G__ and __H__, let __f__(__G__,__H__) denote the minimum integer __n__ such that in every coloring of the edges of __K__~__n__~, there is either a copy of __G__ with all edges having the same color or a copy of __H__ with all edges having different colors. We show tha

Mixed ramsey numbers: Chromatic numbers

Mixed ramsey numbers: Chromatic numbers versus graphs

✍ James M. Benedict; Gary Chartrand; Don R. Lick 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 399 KB