A Ramsey-Type Theorem for Orderings of a Graph
A Ramsey-Type Theorem for Orderings of a Graph
复制标题
图序的拉姆齐型定理
DOI：
10.1137/0402035
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
P. Winkler
中科院分区：
文献类型：
--
作者：
V. Rödl;P. Winkler
证明了对任意n阶图G，存在一个阶至多为$n^3（\log n）^2 $的数N和一个n阶图H，使得对G的任意顶点序和H的任意顶点序，存在从G到H的序同构.
It is shown that for any graph G on n vertices, there is a number N (of order at most $n^3 (\log n)^2 $) and a graph H on N vertices such that for any ordering of the vertices of G and any ordering of the vertices of H, there is an order-isomorphism from G into H.