𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sparse ramsey graphs

✍ Scribed by Jaroslav Nešetřil; Vojtěch Rödl

Book ID
110564213
Publisher
Springer-Verlag
Year
1984
Tongue
English
Weight
346 KB
Volume
4
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Sparse Anti-Ramsey Graphs
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.

Ramsey numbers for sparse graphs
Ramsey numbers for sparse graphs
✍ Nancy Eaton 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 512 KB

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

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

On the Ramsey Number of Sparse 3-Graphs
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
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