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
ALON, N
[J]. JOURNAL OF GRAPH THEORY, 1994, 18 (04) : 343 - 347
[2] EXPLICIT CONSTRUCTION OF LINEAR SIZED TOLERANT NETWORKS
ALON, N
CHUNG, FRK
[J]. 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.
BECK, J
[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
CHVATAL, C
RODL, V
SZEMEREDI, E
TROTTER, WT
[J]. 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 →