Remarks on the size Ramsey number of graphs
Remarks on the size Ramsey number of graphs
复制标题
关于拉姆齐图数大小的备注
DOI：
--
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
H. Bielak
中科院分区：
文献类型：
--
作者：
H. Bielak
AbstractIn this paper we prove that the cyclomatic number of a graph whose every 2-edgecolouring contains a monochromatic path witht edges is not less than 3t/4 − 2. This fact leads to a simple non-probabilistic proof of the following theorem of Beck:
$$egin{array}{*{20}c} {lim inf{{hat rleft( {P_t }
ight)} mathord{left/ {vphantom {{hat rleft( {P_t }
ight)} t}}
ight. kern-
ulldelimiterspace} t} geqslant {9 mathord{left/ {vphantom {9 4}}
ight. kern-
ulldelimiterspace} 4},} & {t o infty ,} \ end{array}$$
where
$$hat r(P_t )$$
is the size Ramsey number of a pathPt ont edges. We also show that the size Ramsey number of a (q + 1)-edge star with a tail of length one equals 4q − 2, i.e., it is linear on the number of edges of the graph. Finally, we calculate that the upper bound for the size Ramsey number of a (q + 2)-edge star with a tail of length two is not greater than 5q + 3.
AbstractIn this paper we prove that the cyclomatic number of a graph whose every 2-edgecolouring contains a monochromatic path witht edges is not less than 3t/4 − 2. This fact leads to a simple non-probabilistic proof of the following theorem of Beck:
$$egin{array}{*{20}c} {lim inf{{hat rleft( {P_t }
ight)} mathord{left/ {vphantom {{hat rleft( {P_t }
ight)} t}}
ight. kern-
ulldelimiterspace} t} geqslant {9 mathord{left/ {vphantom {9 4}}
ight. kern-
ulldelimiterspace} 4},} & {t o infty ,} \ end{array}$$
where
$$hat r(P_t )$$
is the size Ramsey number of a pathPt ont edges. We also show that the size Ramsey number of a (q + 1)-edge star with a tail of length one equals 4q − 2, i.e., it is linear on the number of edges of the graph. Finally, we calculate that the upper bound for the size Ramsey number of a (q + 2)-edge star with a tail of length two is not greater than 5q + 3.