集染色顶点和集染色边的Folkman数

对于给定的简单图G和正整数a1,a2,…,ak,G→(a1,a2,…,ak)vr(G→(a1,a2,…,ak)er)是指,对于V(G)(E(G))的任意k-染色,其中每个顶点(边)被用{1,…,k}的一个r-子集来染色,存在i∈{1,…,k}和一个阶为ai的完全子图,其中每个顶点(边)被一个包含颜色i的r-子集染色.本文在整数t>max{a1,a2,…,ak}的条件下,定义并研究下述集染色顶点(边)Folkman数:F(r)v(a1,a2,…,ak;t)=min{|V(G)|:G→(a1,a2,…,ak)vr且KtG}(类似地,F(r)e(a1,a2,…,ak;t)=min{|V(G)|:G→(a1,a2,…,ak)er且KtG}).     

关于顶点Folkman数的新不等式

对于无向简单图G及正整数a1,…,ak,记G→(a1,…,ak)v当且仅当对于图G的任意一种顶点k染色,一定对某个i∈{1,…,k}存在顶点全染着颜色i的完全子图Kai.对于p>m ax{a1,…,ak},定义Fv(a1,…,ak;p)=m in{V(G):G→(a1,…,ak)v,Kp G}为顶点Folkm an数.证明关于顶点Folkm an数Fv(k,k;k 1)的新的迭代不等式,并推广K olev和N enov的一个关于多色顶点Folkm an数的不等式.     

顶点Folkman数的上界

证明关于顶点Folkman数上界的新不等式.特别地,用构造性方法证明:对于任意满足00和c(r)>0使得Fv(k,k;k 1)≤c(r)(k-1)1/4log2(k-1)-r对任意的k≥N(r)成立,其中N(r)和c(r)都是只依赖于r的常数.     

集染色顶点和集染色边的Folkman数（英文）

对于给定的简单图G和正整数a1,a2,…,ak,G→(a1,a2,…,ak)vr(G→(a1,a2,…,ak)er)是指,对于V(G)(E(G))的任意k-染色,其中每个顶点(边)被用{1,…,k}的一个r-子集来染色,存在i∈{1,…,k}和一个阶为ai的完全子图,其中每个顶点(边)被一个包含颜色i的r-子集染色.本文在整数tmax{a1,a2,…,ak}的条件下,定义并研究下述集染色顶点(边)Folkman数:F(r)v(a1,a2,…,ak;t)=min{|V(G)|:G→(a1,a2,…,ak)vr且KtG}(类似地,F(r)e(a1,a2,…,ak;t)=min{|V(G)|:G→(a1,a2,…,ak)er且KtG}).     

用构造性方法计算多重图Ramsey数的界

在图的边染色问题中,通常考虑的是每条边染且只染一种颜色.边的集染色是这种边染色的一种推广,使每条边对应的不一定是一种颜色,而是给定的颜色集的一个子集.多重图的边染色与边的集染色是等价的.多重图Ramsey数是经典Ramsey数的一种自然的推广,它是通过把完全图的边染色推广到完全多重图的边染色实现的.计算Ramsey数的准确值是NP难题,求多重图Ramsey数的准确值往往更加困难.用一些研究经典Ramsey数的方法来研究2-多重图Ramsey数的界,利用构造性方法证明了一些关于不同参数的2-多重图Ramsey数的不等式,并在此基础上得出了一些小参数多重图Ramsey数的准确值或上下界.     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

一类特殊图的顶点染色数

如果图G含有的所有最大团存在公共顶点,且公共顶点的个数为κ,就称此图为第κ类图。据此,本文给出了研究图的顶点染色的一种新方法,并以此研究了一类特殊图的顶点染色及一些图的顶点染色数。     

关于边染色临界图的独立数

1968年,Vizing提出猜想:边染色临界图的独立数不大于其阶数的一半.针对不含2度点的边染色临界图,本文证明当最大度为9,10时,独立数α(G)≤(3△-3)/(5△-3)|V|和当△∈{11,…,46}时,独立数α(G)≤(15△-42)/(23△-42)|V|.     

De Bruijn图的均匀顶点染色和有向图线图的一个顶点染色定理

给出了ｎ维ｄ进位Ｄｅ Ｂｒｕｉｊｎ图Ｂ（ｄ，ｎ）的一种均匀顶点ｄ＋１染色，即将其顶点集分拆成顶点个数至多相差１的ｄ＋１个无关集，并证明了关于一般有向图的线图的一个顶点染以定理。     

边染色临界图主顶点数的一个结果

如果一个连通的第二类图G去掉任意一条边后其边色数都比图G小,则称它是一个临界图.最大顶点度为△的临界图称作△-临界图.1968年,Vizing猜想任意n阶△-临界图G边数m的下界为（nΔ-n＋3）/2.Fiorini不等式和差值转移法被广泛用于研究此猜想.笔者利用Vizing邻接引理和临界图的结构性质给出了Δ-临界图在△≥6且（Δ-1）度顶点至多邻接一个四度顶点时Fiorini不等式的一个新的下界.     

3个关于K4-e的Ramsey数

给出求双色Ramsey数R（G1,G2）准确值的一个算法,并利用该算法计算得到3个关于K4-e的Ramsey数的精确值：R（K4-P,K2．3）=10,R（K4-e,K2．4）=13,R（K4-P,K2．5）=16．     

关于路与偶圈的6个广义Ramsey数的值

给出求R(G1,G2,G3)的一个算法,并利用它得到6个广义Ramsey数的值:R(P4,C4,C4)=9,R(P4,C4,C6)=9,R(P4,C6,C6)=9,R(P5,C4,C4)=11,R(P5,C4,C6)=9,R(P5,C6,C6)=11.     

关于全着色Ramsey数

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

Wm V C3的点可区别正常边色数

对于轮和圈的联图,给出了一种点可区别的边染色方法,并得到了其点可区别边色数．     

关于不冗余的Ramsey数的性质

不冗余的(irredundant)Ramsey数与著名的Ramsey数有着密切的关系,对它的研究将能得到Ramsey数的下界结果.在前人工作的基础上,对不冗余的Ramsey数进行了研究,得到了两个关于Ramsey数性质的结果,并由此得到了一个不冗余的Ramsey数的下界公式,此公式同时也就是Ramsey数的下界公式.     

Ramsey数R(K_3,K_q-e)

利用一种系统地构造循环着色的算法,借助计算机证明了Ｒａｍｓｅｙ数Ｒ（Ｋ３,Ｋｑ－ｅ）的下述新下界：Ｒ（Ｋ３,Ｋ１１－ｅ）≥４２,Ｒ（Ｋ３,Ｋ１３－ｅ）≥５４,Ｒ（Ｋ３,Ｋ１４－ｅ）≥５９,Ｒ（Ｋ３,Ｋ１５－ｅ）≥６９。     

边Ramsey上界研究

对于无向有限简单图G和H,边Ramsey数R(C,H)是指最小的整数e,使得对一个有e条边的图的边用红蓝两色进行2-染色后要么得到一个红色的G,要么得到一个蓝色的H.通过分支定界法,得到一些边Ramsey数的上界.