✦ LIBER ✦

On graphs with small Ramsey numbers

✍ Scribed by A. V. Kostochka; V. Rödl

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

No coin nor oath required. For personal study only.

✦ Synopsis

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,γ) such that for every bipartite graph G = (W,U;E) with the maximum degree of vertices in W at most d and $|U|\leq |W|^{\gamma }$, $R(G)\leq k|W|$. This answers a question of Trotter. We give also a weaker bound on the Ramsey numbers of graphs whose set of vertices of degree at least d + 1 is independent. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 198–204, 2001

📜 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

Diagonal Ramsey numbers for small graphs

✍ S. A. Burr 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB

Size Ramsey numbers for small-order grap

Size Ramsey numbers for small-order graphs

✍ R. J. Faudree; J. Sheehan 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

A table of the size Ramsey number or the restricted size Rarnsey number for all pairs of graphs with at most four vertices and no isolated vertices is given. Let F, G, and H be finite, simple, and undirected graphs. The number of vertices and edges of a graph F are denoted byp(F) and q(F), respecti

On irredundant Ramsey numbers for graphs

✍ Johannes H. Hattingh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 248 KB

## Abstract The irredundant Ramsey number __s(m, n)__ is the smallest p such that in every two‐coloring of the edges of __K~p~__ using colors red (__R__) and blue (__B__), either the blue graph contains an __m__‐element irredundant set or the red graph contains an __n__‐element irredundant set. We

Graphs with Linearly Bounded Ramsey Numb

Graphs with Linearly Bounded Ramsey Numbers

✍ G.T. Chen; R.H. Schelp 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 439 KB

A graph $G$ of order $n$ is $p$-arrangeable if its vertices can be ordered as $v_{1}, v_{2}, \ldots, v_{n}$ such that $\left|N_{L_{i}}\left(N_{R_{i}}\left(v_{i}\right)\right)\right| \leqslant p$ for each $1 \leqslant i \leqslant n-1$, where \(L_{i}=\left\{v_{1}, v_{2}, \ldots, v_{i}\righ

On ramsey-tuŕan numbers for 3-graphs

✍ A. F. Sidorenko 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract For every __r__‐graph __G__ let π(__G__) be the minimal real number ϵ such that for every ϵ < 0 and __n__ ϵ __n__~0~(λ, __G__) every __R__‐graph __H__ with __n__ vertices and more than (π + ϵ)(nr) edges contains a copy of __G__. The real number λ(__G__) is defined in the same way, addin