✦ LIBER ✦

Linear Ramsey numbers of sparse graphs

✍ Scribed by Lingsheng Shi

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 102 KB
Volume: 50
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20103

No coin nor oath required. For personal study only.

✦ Synopsis

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 settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

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

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

Sparse Anti-Ramsey Graphs

✍ Y. Kohayakawa; T. Luczak 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 269 KB

It is shown that for every $l \geqslant 3$ there exists a graph $G$ of girth / such that in any proper edge-colouring of $G$ one may find a cycle of length / all of whose edges are given different colours. 1995 Academic Press. Inc.

Independence numbers of locally sparse g

Independence numbers of locally sparse graphs and a Ramsey type problem

✍ Noga Alon 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 409 KB 👁 1 views

Let G = (V, E ) be a graph on n vertices with average degree t 2 1 in which for every vertex u E V the induced subgraph on the set of all neighbors of u is r-colorable. We show that the independence number of G is at least log t , for some absolute positive constant c. This strengthens a well-known

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

Irredundant ramsey numbers for graphs

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