𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generalizations of a Ramsey-theoretic result of chvátal

✍ Scribed by Stefan A. Burr; Paul Erdös

Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
619 KB
Volume
7
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Chvátal has shown that if T is a tree on n points then r(K~k~, T) = (k – 1) (n – 1) + 1, where r is the (generalized) Ramsey number. It is shown that the same result holds when T is replaced by many other graphs. Such a T is called k‐good. The results proved all support the conjecture that any large graph that is sufficiently sparse, in the appropriate sense, is k‐good.

📜 SIMILAR VOLUMES

A ramsey-theoretic result involving chro
A ramsey-theoretic result involving chromatic numbers
✍ Stefan A. Burr 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB

## Abstract The following result is proved. A graph __G__ can be expressed as the edge‐disjoint union of __k__ graphs having chromatic numbers no greater than __m__~1~,…,__m__~__k__~, respectively, iff χ(__G__) ≤ __m__~1~…__m__~__k__~.