The size-Ramsey number of trees

被引：15

作者：

Dellamonica, Domingos, Jr. ^{[1
]}

机构：

[1] Emory Univ, Dept Math, Atlanta, GA 30322 USA

来源：

RANDOM STRUCTURES & ALGORITHMS | 2012年 / 40卷 / 01期

关键词：

size-Ramsey number; trees; expander graphs; BOUNDED DEGREE; GRAPHS;

D O I：

10.1002/rsa.20363

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given a graph G, the size-Ramsey number (r) over cap (G) is the minimum number m for which there exists a graph F on m edges such that any two-coloring of the edges of F admits a monochromatic copy of G. In 1983, J. Beck introduced an invariant beta(.) for trees and showed that (r) over cap (T) = Omega(beta(T)). Moreover he conjectured that (r) over cap (T) = Theta(beta(T)). We settle this conjecture by providing a family of graphs and an embedding scheme for trees. (C) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 49-73, 2012

引用

页码：49 / 73

页数：25

共 10 条

[1] ON SIZE RAMSEY NUMBER OF PATHS, TREES, AND CIRCUITS .1. [J].