✦ LIBER ✦

Ramsey numbers for sparse graphs

✍ Scribed by Nancy Eaton

Book ID: 104113970
Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 512 KB
Volume: 185
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00184-2

No coin nor oath required. For personal study only.

✦ Synopsis

We consider a class of graphs on n vertices, called (d,f)-arrangeable graphs. This class of graphs contains all graphs of bounded degree d, and all df-arrangeable graphs, a class introduced by Chen and Schelp in 1993. In 1992, a variation of the Regularity Lemma of Szemer6di was introduced by Eaton and RSdl. As an application of this lemma, we give a linear upper bound, c(d, f)n, for the Rarnsey number of graphs in this class, where log 2 log 2 c(d, f) = 24df 5.

This improves the earlier result, given in 1983 by Chv~tal et al. of a linear bound on the Ramsey number of graphs with bounded degree d, where the constant term was more that a tower of d 2's, and later extended by Chen and Schelp to include d-arrangeable graphs.

📜 SIMILAR VOLUMES

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

On the Ramsey Number of Sparse 3-Graphs

✍ Brendan Nagle; Sayaka Olsen; Vojtěch Rödl; Mathias Schacht 📂 Article 📅 2008 🏛 Springer Japan 🌐 English ⚖ 246 KB

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.

Irredundant ramsey numbers for graphs

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

Lower Ramsey numbers for graphs

✍ C.M. Mynhardt 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 380 KB

Let p(G) denote the smallest number of vertices in a maximal clique of the graph G, while i(G) (the independent domination number of G) denotes the smallest number of vertices in a maximal independent (i.e. independent dominating) set of G. For given integers 1 and m, the lower Ramsey number s(l, m)

CO-irredundant Ramsey numbers for graphs

✍ E. J. Cockayne; G. MacGillivray; J. Simmons 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 2 views