𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Induced Ramsey Numbers for Graphs with Bounded Maximum Degree

✍ Scribed by Tomasz Łuczak; Vojtěch Rödl

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
435 KB
Volume
66
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

For graphs G and H we write G wÄ ind H if every 2-edge colouring of G yields an induced monochromatic copy of H. The induced Ramsey number for H is defined as r ind (H)=min[ |V(G)|: G wÄ ind H]. We show that for every d 1 there exists an absolute constant c d such that r ind (H n, d ) n cd for every graph H n, d with n vertices and the maximum degree at most d. This confirms a conjecture suggested by W. T. Trotter.

📜 SIMILAR VOLUMES

Total interval number for graphs with bo
Total interval number for graphs with bounded degree
✍ Kostochka, Alexander V.; West, Douglas B. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 2 views

The total interval number of an n-vertex graph with maximum degree ∆ is at most (∆+1/∆)n/2, with equality if and only if every component of the graph is K ∆,∆ . If the graph is also required to be connected, then the maximum is ∆n/2 + 1 when ∆ is even, but when ∆ is odd it exceeds [∆ + 1/(2.5∆ + 7.7