广义Ramsey数R(K_3,K_(21)-e)和(K_3,K_(22)-e)的新下界

研究了完全图的循环着色,得到了广义Ramsey数R(K3,Kq-e)的两个新下界:R(K3,K21-e)≥111、R(K3,K22-e)≥122.

三个广义Ramsey数的新下界

研究了完全图的循环着色,提出了完全图循环着色的一种算法,得到了广义Ramsey数R(K3,Kq-e)的三个新下界:R(K3,K17-e)≥80、R(K3,K18-e)≥92、R(K3,K20-e)≥106.

一个广义Ramsey数r(C_5 ,K_7)(英文)

该文证明了 2 5 ≤r(C5,K7) ≤ 2 6 .

关于广义Ramsey数

我们知道古典的Ramsey数具有非常深刻的组合意义,但这些整数的确定却相当困难。 1967年以后人们引进了各种广义Ramsey的概念。1978年,PErdo引进了Size Ramsey数,这里我们将给出几类图对的Size Ramsey数,顺便也对另一种广义Ramsey数:Diagonal Ramsey数进行一些讨论。 本文中所用的没有定义的记号可参见[3]。

一类广义Ramsey数R(B2,Kn)界的研究

Ramsey数的确定是一个非常困难并尚未完全解决的问题.利用构造特殊图的方法准确界定Ramsey数,目前只解决了较少的经典Ramsey数.经典Ramsey数R(4,n)目前已有的界均为组合数形式或者递推式,均为构造特殊图的方法得出.文章主要利用概率的方法给出了一类广义Ramsey数R(B2,Kn)的非线性界.由于B2是完全图K4的子图,因此上述非线性界同样也适用于R(4,n).

混合Ramsey数x_2(m,P_n)的下界

以 X_2(G)记一图 G 之全色数,P_n 表示 n 阶路,全色数与路的混合 Ramsey数 X_2(m,P_n)为最小正整数 p,对干每个 p 阶图 G,或者 X_2(G)≥m,或者补图 P_N,Clcves 和 Jacobson 曾得到 n≥2m-2时 X_2(m,P_x)的准确值和 m≤n≤2m-3时X_2(m,P_n)的上、下界.当 n<m 时,X_2(m,P_n)的上界不难得到,笔者将讨论 n<m 时X_2(m,P_n)的下界.

关于全着色Ramsey数

以χ２（Ｇ）记一图Ｇ之全色数，全着色Ｒａｍｓｅｙ数χ２（ｍ，ｎ）为最小正整数ｐ，使得每一ｐ阶图Ｇ或有χ２（Ｇ）≥ｍ，或其补图Ｇ满足χ２（Ｇ）≥ｎ。本文给出χ２（ｍ，ｎ）的上。