Planar Ramsey Numbers
Planar Ramsey Numbers
复制标题
DOI：
10.1006/jctb.1993.1070
复制
发表时间：
1993-11
期刊：
影响因子：
--
通讯作者：
R. Steinberg;C. Tovey
中科院分区：
文献类型：
--
作者：
R. Steinberg;C. Tovey
平面Ramsey数PR (k, l) （k, l≥2）是使任何n个顶点的平面图包含k个顶点的完全图或大小为l的独立集的最小整数n。我们找到了所有k和l的PR （k, l）的精确值。本文包括Albertson， Bollobas和Tucker在1976年提出的一个猜想的证明，该猜想认为，每个n个顶点上的无三角形平面图都包含一个大小为⌊n /3⌋+ 1的独立集合。
Abstract The planar Ramsey number PR ( k , l ) ( k , l ≥ 2) is the smallest integer n such that any planar graph on n vertices contains either a complete graph on k vertices or an independent set of size l . We find exact values of PR ( k , l ) for all k and l . Included is a proof of a 1976 conjecture due to Albertson, Bollobas, and Tucker that every triangle-free planar graph on n vertices contains an independent set of size ⌊ n /3⌋ + 1.