Ramsey边线性图的结构特征

图论是组合数学的一个重要分支，近年来图论及其应用的研究得到了飞速的发展.对Ramsey理论的研究是一项既有理论意义，又具有哲学内涵的课题. 它揭示了在一个充分大的系统中某些预先给定的子系统的存在性.本项目拟从研究某些稀疏图的Ramsey数展开，试图刻画Ramsey边线性图的特征，拟研究的主要问题为：问题1.对于边数满足n(G)+1<e(G)<2n(G)-2 的图G，哪些图是Ramsey边线性的, 哪些图不是Ramsey边线性的？问题2. 把4阶完全图的一条边剖分一次或两次后得到的图是否是Ramsey 边线性的？问题3.设G是Ramsey 边线性图，把G的两个顶点用一条长为2的路连接起来后得到的图是否是Ramsey 边线性的？问题4.如果G不含割点且最小度大于等于3，那么G是否一定不是Ramsey边线性的？如果问题3和问题4的回答都是肯定的，那么我们就完全刻画了Ramsey边线性图的特征。

在本项目中，我们从一些特殊图的Ramsey数及平面Ramsey数入手, 试图解决一些图的 Ramsey 边线性问题。 利用图的边数与围长, 边数与泛圈性的关系，以及一个图与其补图的围长之间的关系，完全解决了Surahmat 等人关于大圈对奇阶数轮的猜想。本项目还确定了其他几类圈-轮型 Ramsey 数的值，确定了一些扇-轮型 Ramsey 数的值。在平面 Ramsey 数方面，确定了完全图-轮型平面 Ramsey 数，及 4圈-完全图的平面 Ramsey 数。我们还研究了与 Ramsey 边线性问题关系密切的图的划分问题，部分地证明了Arkin 和 Hassin 的一个猜想。 这些成果为解决 Ramsey 边线性问题奠定了基础。