几类特殊图的圆色数性质

圆色数是图的色数概念的推广 .与色数相比 ,圆色数包含了更多有关图本身结构的信息 ,因而更加难以确定 .本文推导了 2类特殊图———图Ctk 和图Ctk-v的圆色数 ;并给出了图Hm ,n圆色数的一个简单证明 .     

一类距离图的圆色数

圆色数是图的一个重要参数 .距离图G(Z ,D)是具有顶点集Z ={ 0 ,± 1,± 2 ,… }、距离集D ,且满足顶点x与y相邻的充要条件是y -x∈D的无限图 .本文确定了两类距离图G(Z ,Dm ,k ,k + 1)和G(Z ,Dm ,k ,k + 1.k + 2 )的圆色数 .     

禁用子图为2K_2和K_1+C_4的图的色数

通过对禁用子图为2K_2和K_1+C_4的图的结构进行分析,利用强完美图定理,得到了该类图色数的一个关于团数的线性函数的上界。此结果是对Wagon关于2K_2结论的精细刻画,是Gyárfás猜想的特殊类型。     

从地图的形成原理看“图论”证明方法的缺陷——兼对地图仅需着色种数的证明

本文以地图的形成原理为切入点,遵循整体元素循序逐增这一地图形成的基本原理,求证到地图的结构模式是C2N组合模式;又从地图的C2N组合模式中发现了破解四色猜想命题的金钥匙;本文还将整体元素循序逐增基本原理与图论的两点连线证明方法进行对接,证明本人的证明结果与正确应用两点连线证明方法的证明结果相同,找到了图论应用两点连线证明方法时存在的三大缺陷.     

SP图簇h（G m（r,n+1））的伴随多项式的因式分解及其补图的色等价性

本文利用图的伴随多项式的性质及其伴随分解的图论方法,讨论了h(G而证明了在不同条件下这类图的补图的色等价性。 m(r,n+1))型图的伴随多项式的因式分解,进而证明了在不同条件下这类图的补图的色等价性。     

一种构造k—色临界图的方法

图G的色数χ(G)是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有χ(H)<χ(G)=k,则称G是k—色临界的,因此可以给出一种构造k—色临界图的方法。     

禁用子图为P3∪mP2的图色数上界

Gyárfás在完美图概念的基础上,提出了色界函数的概念,并给出猜想：对于给定的森林F,存在整数函数f (F, x)使得每一个以F为禁用子图的图G都满足χ(G)≤f (F,ω(G)),其中χ(G)和ω(G)分别表示图G的色数和团数。通过分析禁用子图为P₃∪P₂的图结构,给出色界函数f (P₃∪P₂,ω(G))的一个上界;并且以此为基础,得到禁用子图为P₃∪mP₂的图色数上界。     

梯图L_n的r(2)点染色

利用图的(r2)点染色的概念,研究了梯图L n的(r2)点染色问题,并得到了它们的(r2)点色数.     

一种构造k-色临界图的方法

图G的色数Х（G）是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有Х（H）〈Х（G）=k,则称G是k-色临界的,因此可以给出一种构造k-色临界图的方法。     

图K+sm+1(m,m+1)的色唯一性

设G是一个图,用P(G,λ)表示图G的色多项式,称图G与H是色等价的,如果P(G,λ)=P(H,λ),记为H～G.本文证明了m≥s+2且s≥1,S是Kms+1的某s条边组成的集合且S在Km+1中的导出子图〈S)是二部图,则[K+sm+1(m,m+1)]={N=V G| G∈[--Km+1-s]}色唯一当且仅当〈S〉是2-连通且是色唯一的     

禁用子图为C_4和K_1∪P_4的图色数上界

利用图的结构分析法,得到了禁用子图为C_4和K_1∪P_4的图的一个结构定理,根据强完美图定理,得到了该类图色数的一个关于团数的线性函数的上界。进一步得到了禁用子图为2K_2和K_1+P_4的图色数上界,此结果是对Wagon关于2K_2结论的精细刻画,是Gyárfás猜想的特殊类型。     

一类R(G)=-2图簇的补图的色性

研究不可约图的补图的色唯一性问题是图论的一个重要内容，该文在论证过程中利用图G的伴随多项式的最小根的性质及比较伴随多项式的末项。找到了一类n个点n l条边且R(G)：-2的图簇。其补图是色唯一的。主要结论是如下定理：设|V(A3(r1,r2))|=n(≥10)，其中r1≥3，r2≥5。若r2=5且A3(r1,r2)不可约，则A3(^→r1，r2)是色唯一的。即A3(^→r1，5)是色唯一的。     

一类图的补图的色唯一性

本文通过引入P_(n9)C_(n9)和T_(1,a,b)的伴随多项式的代数性质,讨论形如■的补图的色性,并证明了,在一定的限制条件下,它们是色唯一图.     

图Km＋1^＋s（m,m＋1）的色唯一性

设G是一个图，用P（G，λ）表示图G的色多项式，称图G与H是色等价的，如果P（G，λ)=P(H,λ）,记为H-G。本证明了m≥s 2且s≥1,S是Km 1的某s条边组成的集合且S在Km 1中的导出子图（S）是二部图。则[Km 1^ s（m,m 1)]=[NmVG|G∈[kM 1-s]|色唯一当且仅当（S）是2-连通且是色唯一的。     

联图Cn ∨ Kn的全色数

研究了联图Cn∨Kn=2n的全色数,证明了当n≥5时,全色数χT(Cn∨Kn)=2n,从而证明了Cn∨Kn满足全着色猜想.     

恰用m种颜色着色的一类计数问题的算法

用m种不同的颜色对圆内n个扇形染色(相邻扇形不同色)的方法数可用公式表示,其中包含恰用2种、恰用3种、…、恰用m种颜色染色的方法.如果要计算恰用m种不同的颜色对圆内n个扇形染色(相邻扇形不同色)的方法数难度更大.本文用猜想证明和算法程序解决了该问题.     

图的色多项式系数与图的特征关系

研究了连通图周长c(G)(c(G)≥3)与它的色多项式系数a2,a3,L,an的关系,得到一些有用结果,同时也刻画了一些特殊图与它的色多项式系数a2,a3,L,an的对应关系.     

关于一类R(G)=-2类图簇补图的色性

研究不可约图的补图的色唯一性问题是图论的一个重要内容,该文在论证过程中利用图G的伴随多项式的末项的特点,通过比较伴随多项式的末项,探讨了一类n个点n+1条边且R(G)=-2的不可约图的补图的色唯一性的问题,并推广了文[8]中的结论.在本文中,我们得到如下结论设IV(B1)I=n(＞8),若B1是不可约,则(-B1)是色唯一的.     

一类6-正则循环图的点色数

运用图的分数染色讨论了一类6-正则循环图的顶点染色,得到了邻接矩阵的首行具有形式(01110…0111)的n阶循环图G点色数:X(G)={4,4|n5,其它.     

几类含两个圈且R(G)=-2图的补图的色性

将点数为n，边数为n 1(即图中含有两个圈）且R（G）=-2的连通图合称为N类图，我们根据它们的伴随多项式的第四项系数b3的大小，将N类图分为如下图簇；N0，N1，N2，N3，N4，利用图的伴随多项式的最小根的性质及比较伴随多项式的末项系数，讨论了N3，N4类不可约图的色等价性及色唯一性的问题。