ON PARTITION THEOREMS FOR FINITE GRAPHS
ON PARTITION THEOREMS FOR FINITE GRAPHS
复制标题
DOI：
--
复制
发表时间：
1973
期刊：
影响因子：
--
通讯作者：
P. E. -. R. L. Graham
中科院分区：
文献类型：
--
作者：
P. E. -. R. L. Graham
对于给定的有限图G和正整数k，设r（G ; k）表示最小整数r，使得如果r个顶点上的完全图Kr的边被任意划分为k个类，则某类包含与G同构的子图. r（G ; k）的存在性立即从著名的定理R amsey {8]得出，该定理断言r（Kn ; k）<对于所有n和k。在本文中，我们研究了r（G ; k）的行为，大k作为G的范围在各种类型的图。
For a given finite graph G and positive integer k, let r(G ; k) denote the least integer r such that if the edges of Kr , the complete graph on r vertices, are arbitrarily partitioned into k classes then some class contains a subgraph isomorphic to G . The existence of r(G ; k) follows at once from the well-known theorem of R a m s e y {8] which asserts that r(Kn ; k) < for all n and k . In this paper we investigate the behavior of r(G ; k) for large k as G ranges over various classes of graphs .