Ramsey极图的性质

本文在引进Ｒａｍｓｅｙ数Ｒ（ｍ，ｎ）的饱和极图Ｇ（ｍ，ｎ）的概念后，证明了Ｇ（３，ｎ）中每个顶点必至少是一个五边形的顶点以及Ｇ（３，ｎ）中至少含有个互不相交的五边形等定理；最后还证明了一个新的下界定理，从而改进了一批Ｒａｍｓｅｙ数的下界，例Ｒ（４，１５）≥１２２，Ｒ（５，９）≥９９等．

关于图色常量的Shen Lin和Irving界

令阿Ａｒ＝（ａ_１，ａ_２，…，ａ_ｒ），其中整数ａ_ｉ≥２，ｒ≥１.所谓图Ｇ的Ａｒ着色即对 图Ｇ的边用不同的颜色ｃ_1ｃ_2,…,ｃ_ｒ着色，使得没有一个ａ_ｉ个顶点的完全子 图的所有边都着色ｃ_ｉ（ｉ＝１，２，…，ｒ）．令ＨlＮ为具有Ｎ个顶点但不包含l个顶 点的完全子图的图的集合，Ｎ（Ａr,l）表示Ｇ∈ＨlＮ但不能被 Ａ 着色的图具有的 最少顶点数。本文定义一种临界图，并在此基础上利用Ｈ５（Ｎ－１）的临界图构造Ｈ５Ｎ 的临界图。通过证明Ｈ５（１２）的临界图均能（３，３）着色，证明Ｈ５（１２）中的图均能（３，３） 着色，进而得出：１３＜Ｎ（（３，３），５）＜１８，优于前人得出的１０＜Ｎ（（３，３），５）＜１８的结 果．