𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the minimum degree of minimal Ramsey graphs

✍ Scribed by Tibor Szabó; Philipp Zumstein; Stefanie Zürcher

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
145 KB
Volume
64
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We investigate the minimization problem of the minimum degree of minimal Ramsey graphs, initiated by Burr et al. We determine the corresponding graph parameter for numerous bipartite graphs, including bi‐regular bipartite graphs and forests. We also make initial progress for graphs of larger chromatic number. Numerous interesting problems remain open. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 150–164, 2010

📜 SIMILAR VOLUMES

The minimum degree of Ramsey-minimal gra
The minimum degree of Ramsey-minimal graphs
✍ Jacob Fox; Kathy Lin 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract We write __H__ → __G__ if every 2‐coloring of the edges of graph __H__ contains a monochromatic copy of graph __G__. A graph __H__ is __G__‐__minimal__ if __H__ → __G__, but for every proper subgraph __H__′ of __H__, __H__′ ↛ __G__. We define __s__(__G__) to be the minimum __s__ such th

On k-domination and minimum degree in gr
On k-domination and minimum degree in graphs
✍ Odile Favaron; Adriana Hansberg; Lutz Volkmann 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

## Abstract A subset __S__ of vertices of a graph __G__ is __k__‐dominating if every vertex not in __S__ has at least __k__ neighbors in __S__. The __k__‐domination number $\gamma\_k(G)$ is the minimum cardinality of a __k__‐dominating set of __G__. Different upper bounds on $\gamma\_{k}(G)$ are kn

Graph decomposition with constraints on
Graph decomposition with constraints on the connectivity and minimum degree
✍ Carsten Thomassen 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

## Abstract For each pair __s,t__ of natural numbers there exist natural numbers __f(s,t)__ and __g(s,t)__ such that the vertex set of each graph of connectivity at least __f(s,t)__ (respectively minimum degree at least __g(s,t))__ has a decomposition into sets which induce subgraphs of connectivit

On Induced Ramsey Numbers for Graphs wit
On Induced Ramsey Numbers for Graphs with Bounded Maximum Degree
✍ Tomasz Łuczak; Vojtěch Rödl 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 435 KB

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