✦ LIBER ✦

Constrained Ramsey numbers of graphs

✍ Scribed by Robert E. Jamison; Tao Jiang; Alan C. H. Ling

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 135 KB
Volume: 42
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10072

No coin nor oath required. For personal study only.

✦ Synopsis

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 that f(G,H) is finite iff G is a star or H is acyclic. If S and T are trees with s and t edges, respectively, we show that 1+s(t−2)/2≤f(S,T)≤(s−1)(t^2^+3__t__). Using constructions from design theory, we establish the exact values, lying near (s−1)(t−1), for f(S,T) when S and T are certain paths or star‐like trees. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 1–16, 2003

📜 SIMILAR VOLUMES

Irredundant ramsey numbers for graphs

✍ R. C. Brewster; E. J. Cockayne; C. M. Mynhardt 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 356 KB

Mixed ramsey numbers: Chromatic numbers

Mixed ramsey numbers: Chromatic numbers versus graphs

✍ James M. Benedict; Gary Chartrand; Don R. Lick 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 399 KB

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

Anti-Ramsey Numbers of Subdivided Graphs

✍ Tao Jiang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 88 KB

Given a positive integer n and a family F of graphs, the anti-Ramsey number f(n, F) is the maximum number of colors in an edge-coloring of K n such that no subgraph of K n belonging to F has distinct colors on its edges. The Tura ´n number ex(n, F) is the maximum number of edges of an n-vertex graph

Constrained Ramsey numbers for rainbow m

Constrained Ramsey numbers for rainbow matching

✍ Allan Siu Lun Lo 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB

The Ramsey number R k (G) of a graph G is the minimum number N, such that any edge coloring of K N with k colors contains a monochromatic copy of G. The constrained Ramsey number f (G, T ) of the graphs G and T is the minimum number N, such that any edge coloring of K N with any number of colors con

CO-irredundant Ramsey numbers for graphs

✍ E. J. Cockayne; G. MacGillivray; J. Simmons 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 2 views