Distance Preserving Ramsey Graphs
Distance Preserving Ramsey Graphs
复制标题
距离保持拉姆齐图
DOI：
10.1017/s096354831200003x
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
V. Rödl
中科院分区：
文献类型：
--
作者：
D. Dellamonica;V. Rödl
我们证明了以下度量拉姆齐定理。对于任何在其顶点集上赋予线性序的连通图G，存在一个图R，使得在R的顶点t集的每个着色中，都有可能在R内找到G的副本G*，满足：· distG*（x，y）= distR（x，y）对于每个x，y ∈ V（G*）;·G* 中每个t-集的颜色仅取决于有序t-集在G中引入的图距离度量。
We prove the following metric Ramsey theorem. For any connected graph G endowed with a linear order on its vertex set, there exists a graph R such that in every colouring of the t-sets of vertices of R it is possible to find a copy G* of G inside R satisfying: • distG*(x, y) = distR(x, y) for every x, y ∈ V(G*);• the colour of each t-set in G* depends only on the graph-distance metric induced in G by the ordered t-set.