Article contents
Distance Preserving Ramsey Graphs
Published online by Cambridge University Press: 23 April 2012
Abstract
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.
Keywords
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2012
References
- 3
- Cited by