A note on the size-Ramsey number of long subdivisions of graphs

被引：11

作者：

Donadelli, J

Haxell, PE

Kohayakawa, Y

机构：

[1] Univ Fed Parana, Ctr Politecn, Dept Informat, BR-81531980 Curitiba, Parana, Brazil

[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[3] Univ Sao Paulo, Inst Matemat & Estatist, BR-05508900 Sao Paulo, Brazil

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2005年 / 39卷 / 01期

关键词：

The size-Ramsey number; Ramsey theory; expanders; Ramanujan graphs; explicit constructions;

D O I：

10.1051/ita:2005019

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let TsH be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms ( SODA 2002) 321-328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to TsH.

引用

页码：191 / 206

页数：16

共 32 条

[1] SUBDIVIDED GRAPHS HAVE LINEAR RAMSEY NUMBERS [J].

ALON, N .

JOURNAL OF GRAPH THEORY, 1994, 18 (04) :343-347

[2] EXPLICIT CONSTRUCTION OF LINEAR SIZED TOLERANT NETWORKS [J].

ALON, N ;

CHUNG, FRK .

DISCRETE MATHEMATICS, 1988, 72 (1-3) :15-19

[3]

ALON N, 2000, SER DISCRETE MATH OP

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

BECK, J .

JOURNAL OF GRAPH THEORY, 1983, 7 (01) :115-129

[5]

BECK J, 1990, ALGORITHMS COMBINATO, V5, P34

[6] THE RAMSEY NUMBER OF A GRAPH WITH BOUNDED MAXIMUM DEGREE [J].

CHVATAL, C ;

RODL, V ;

SZEMEREDI, E ;

TROTTER, WT .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 34 (03) :239-243

[7]

Diestel R., 1997, Graph Theory

[8]

Erdos P., 1978, Periodica Mathematica Hungarica, V9, P145, DOI 10.1007/BF02018930

[9]

Erdos P., 1975, C MATH SOC J BOLYAI, V10, P515

[10]

Erdos P., 1973, Infinite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai

← 1 2 3 4 →