论文部分内容阅读
Ramsey理论在组合数学中是一个很大很有趣的研究领域,它表达了很深刻的数学思想,大大拓展了鸽笼原理的内涵。Ramsey理论的结果不仅在图论和组合数学中非常重要,在数论,集合论,逻辑学,分析论,代数以及几何学中也有着重要应用。有很多著名的深刻的定理是通过运用Ramsey理论的结果得到的,其中包括Erdos-Rado的典型定理,它将Ramsey原始定理扩展到无限多着色；Shelah定理,它扩展了Hales-Jewett定理(它本身是van derWaerden定理的推广);Galvin,Prikry和Hindman关于无限序列Ramsey性质的定理,以及Gowers的定理,它成功解决了Banach在1932年提出的猜想,即证明了可分的Hibert空间是唯一同构于其所有无限维子空间的Banach空间。
Ramsey理论已向各个方向延伸发展,其中就包括Erdos,Simonovits和Sós在上个世纪七十年代提出的反Ramsey理论。反Ramsey理论研究了在边任意着色即相邻的边也可以有相同的颜色的情况下存在所有边的颜色都不一样的大子图。同时,反Pmmsey数和彩虹数的概念也得到了定义。
而为了研究二部图的强邻边着色,Brualdi和Massey定义了图的关联着色数并用图的最大度对其进行了界定。一个图的关联着色数正好等于它的关联二部图的强邻边着色数。图的强邻边着色即对图的边进行着色以使得着同一颜色的边为图的导出匹配,即此匹配为图的导出子图。强邻边着色数为能使图进行强邻边着色的最小颜色数。
本文分为两个部分,第一部分主要考虑图的彩虹数问题,第二部分主要考虑图的关联着色问题。
第一部分由第二和第三章组成。给定两个图G和H,我们用f(G,H)定义最大的颜色数c,可以用c种颜色对图G进行边着色使得图G的任意H子图至少有两边着同一种颜色。也就是说,任意的用rb(G,H)=f(G,H)+1种颜色对图G进行边着色都会包含一个图G的彩虹子图H。其中彩虹子图为一个任意两边都有不同颜色的子图。数rb(G,H)称为H相对于G的彩虹数。我们简单的用f(n,H)和rb(n,H)分别去表示f(Kn,H)和rb(Kn,H)。数f(n,H)和rb(n,H)分别被简称为图H的反Ramsey数和彩虹数。当G为完全二部图Km,n时,数rb(G,H)被简称为图H的二部彩虹数。
在第二和第三章,我们研究并得到了所有匹配的彩虹数rb(n,kk2)和二部彩虹数rb(Km,n,kK2),其中H=kK2为一个有k条边的匹配M。我们得到如下结果。
1.定义ext(m,n,H)为两部各有m和n点的二部图G(m,n)不包含同构于H的子图所能有的最大边数。对于所有的m≥n≥k≥2,我们有：
2.定义ext(n,H)为n个点的图G不包含同构于H的子图所能有的最大边数。对于所有k≥2,我们有：在第四章,我们研究了图的关联着色。给定图G(V,E),令I(G)={(v,e):v∈V, e∈E,且v与e相关联}为G的关联集。两个关联对(v,e)和(w,f)是相邻的关联对,当且仅当下列三个条件之一成立：(1)v=w,(2)e=f,(3)vw=e或vw=f。我们定义图G的关联着色为对图的关联集进行着色以使得相邻的两个关联对有不同的颜色。关联着色数为使图能关联着色的最小颜色数。我们研究了决定图的关联着色数问题的算术复杂性,得到如下结果。
3.决定半三正则图是否可以4关联着色的是NP-完备的。因此,决定一般图是否可以k关联着色的是NP-完备的,换句话说,决定一般图的关联着色数是NP困难的。