图上点不相交子图的存在性研究

本项目主要研究图中存在点不相交子图的存在性条件，包含最小度条件、邻域并条件以及最小阶数极值条件，探索图上点不相交子图的一般方法。具体研究：（1）无爪图中存在指定结构的点不相交子图的最小阶数极值条件，并设计出相应的算法。进而找到解决特殊图类中存在点不相交子图的一般方法；（2）图中包含点不相交退化圈的泛圈性；（3）图中存在点不相交的长度为偶数的圈的邻域并条件；（4）主要解决Hong Wang在组合杂志上提出的猜想的变式：阶数至少为2R(3,t)(k-1)+1并且最小度至少为3的K_{1,t}-free图包含k个点不相交的三角形，这里，k,t为正整数,R(3,t)表示Ramsey数。并且给出R(3,t)的一些上界。（5）有圈长限制的2-因子和点不相交圈的存在条件；（6）对于阶数充分大的图，运用Szemeredi的正则性引理以及Komlos的放大引理研究存在点不相交圈的最小度条件。

图上点不交子图的存在性问题是图论研究中的基本问题。本项目主要研究图上有限制条件的点不交子图的存在性参数条件，包含最小度、邻域并以及极值参数条件。具体研究内容包括：给出了图上存在点不交偶长圈的邻域并条件；研究了特殊图上存在指定结构的点不交子图个数与其最小度之间的关系，并确定了一般图上有点不交θ图的极值参数；给出了有圈长限制的点不交圈的存在度和条件；证明了4-弧控制有向图中必存在两个长度不同的有向圈，部分地解决了Henning和Yeo的猜测，并借助于无向多重图研究了有向图中点不交的长为4的有向圈的度条件。