𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vertex Ramsey Properties of Families of Graphs

✍ Scribed by Tomasz Łuczak; Andrzej Ruciński; Sebastian Urbański

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
118 KB
Volume
84
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

For graphs F, G 1 , ..., G r , we write F Q (G 1 , ..., G r ) if for every coloring of the vertices of F with r colors there exists i, i=1, 2, ..., r, such that a copy of G i is colored with the ith color. For two families of graphs G 1 , ..., G r and H 1 , ..., H s , by

.., H s ) for every graph F. In this paper, we give necessary and sufficient conditions for (G 1 , ..., G r ) Q (H 1 , ..., H s ) under some weak assumptions on the families of G 1 , ..., G r and H 1 , ..., H s . We also consider the induced version of this problem.

📜 SIMILAR VOLUMES

Ramsey Properties of Families of Graphs
Ramsey Properties of Families of Graphs
✍ Ronald Graham; Tomasz Łuczak; Vojtěch Rödl; Andrzej Ruciński 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 106 KB

For a graph F and natural numbers a 1 ; . . . ; a r ; let F ! ða 1 ; . . . ; a r Þ denote the property that for each coloring of the edges of F with r colors, there exists i such that some copy of the complete graph K ai is colored with the ith color. Furthermore, we write ða 1 ; . . . ; a r Þ ! ðb

Large families of mutually embeddable ve
Large families of mutually embeddable vertex-transitive graphs
✍ Anthony Bonato; Claude Tardif 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 87 KB

## Abstract For each infinite cardinal κ, we give examples of 2^κ^ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all

Constrained Ramsey numbers of graphs
Constrained Ramsey numbers of graphs
✍ Robert E. Jamison; Tao Jiang; Alan C. H. Ling 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract Given two graphs __G__ and __H__, let __f__(__G__,__H__) denote the minimum integer __n__ such that in every coloring of the edges of __K__~__n__~, there is either a copy of __G__ with all edges having the same color or a copy of __H__ with all edges having different colors. We show tha

Generalized Ramsey theory for graphs IV,
Generalized Ramsey theory for graphs IV, the Ramsey multiplicity of a graph
✍ F. Harary; G. Prins 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 412 KB

A paopm graph G has no isolated points. I t s R m e y r u m b a r ( G ) i s the m i n i m p such that every 2-coloring of the edges of K contains a monochromatic G. The Ramhey m & t @ m y R(G) i s P the r (G) ' With j u s t one exception, namely Kq, we determine R(G) f o r proper graphs u i t h a t

Vertex partitions of chordal graphs
Vertex partitions of chordal graphs
✍ David R. Wood 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract A __k‐tree__ is a chordal graph with no (__k__ + 2)‐clique. An ℓ‐__tree‐partition__ of a graph __G__ is a vertex partition of __G__ into ‘bags,’ such that contracting each bag to a single vertex gives an ℓ‐tree (after deleting loops and replacing parallel edges by a single edge). We pro