两类笛卡尔积图的关联色数

Ｒｉｃｈａｒｄ Ａ．Ｂｒｕａｌｄｉ和Ｊ．Ｑｕｉｎｎ Ｍａｓｓｅｙ在（１）中引入了图的关联色数,并且提出了关联色数猜想,即：每一个图Ｇ都可以用Δ（Ｇ）＋种色正常关联着色。本文的主要结果如下：我们不仅证明了路与路,路与圈的笛卡尔积图满足关联色数猜想,进而确定了它们的关联色数。     

图的分散着色和分数色数

引入了一种新的图着色：图的分数关联着色。定义了图的分数关联色数。讨论了分数关联着色的性质,给出了图的分数关联色数的一个下界。     

图的色数问题研究

为了确定任意无向简单图Ｇ从分析点色数的出发，采用了作点集Ｖ的最小划分的方法，得到了一个点色数算法科给出了证明，从而解决了无向简单图的点色数问题。     

图的色数问题研究（续）

进一步研究发现,“图的色数问题研究”一文中的“算法”,实际上是构造图的着色方案的一种算法,也可能得到图的色数,也可能是一种近优值。为了完善该算法,在对不同的最大独立点集进行比较分析后,归纳出存在有多个最大独立点集时,从中选取色数分块的选优准则,并对最大独立点集的有关性质定理作了证明,从而使图的色数算法得以完善。     

两类齿轮图的分数色数

分数着色是在正常着色的基础上提出的,拓展了图着色的研究领域,便于更好的研究图的结构.主要研究了齿轮星图,齿轮风车图的分数色数,分数关联色数和分数全色数,给出了计算这些图形分数色数的公式,并且对公式进行了证明.     

θ-图的对策着色和对策色数

介绍了一种新的二人对策着色:色对策Ⅱ和对策色数Ⅱ.比较了两种色对策的差异,讨论了图G的色对策Ⅱ的性质.在路图和图圈的基础上,利用顶点标号的方法,分别对θ-图和广义θ-图分情况进行了讨论,并得出了它们的对策色数Ⅱ.给出了二人对策着色中使选手A获胜的策略,并推广了此结论.得出了均匀θ-图的对策色数Ⅱ,给出了二人对策着色中选手A的获胜策略.     

一种新的色对策和对策染色数

介绍了一种新的色对策Ⅱ和对策染色数Ⅱ,比较了两种色对策的差异,讨论了图Ｇ的色对策Ⅱ的性质,对这种图的新不变量,利用顶点标号方法,给出获胜策略,对几种特殊图类进行了讨论,分别确定了路图的新不变量,利用顶点标号方法,给出获胜策略,对几种特殊图类进行了讨论,分别确定了路图及补图、圈图Ｃn及与圈有关的图的对策色数Ⅱ。     

局部图的色数算法

本文为无向简单图Ｇ中的局部图ＧＫ的色散ｘ（Ｇｋ）提供了一个算法。     

Halin图的色数问题

Halin图G=T∪C,其中T为每一非悬挂点(内点)度数至少为3的平面树,C为连接T的所有悬挂点的圈.文章分别讨论了Halin图的星色数、面色数及分数色数.     

两类联图的全着色

一个图Ｇ＝（Ｖ，Ｅ）的一个ｋ－全着色是从Ｖ∪Ｅ到Ｉｋ＝｛１，２…ｋ｝上的一个映射ψ；如果对Ｖ∪Ｅ中任意两个相邻或相关联的元素ｅ１，ｅ２，都有ψ（ｅ１）≠ψ（ｅ２）时，则称ψ为Ｇ的一个正规全着色。图Ｇ的全色数定义为ｘＴ（Ｇ）＝ｍｉｎ｛ｋ｜存在Ｇ的一个正规ｋ－全着色｝。令Ｃｎ为ｎ个点的图，Ｋ↑－ｍ为ｍ个点的独立集，Δ为图的最大度。本文证明了在ｍ≠ｎ时联图Ｃｍ＋Ｃｎ的全色数为Δ＋１；在ｍ＋２〈ｎ或ｍ〉ｎ     

几类笛卡尔积图的关联色数研究

图的关联着色问题是图着色理论的重要组成部分之一,确定图的关联色数是一个具有重要的实际价值和理论意义的课题,关于图的关联着色还没有十分深刻的结果,研究了路与完全二部图的笛卡尔积图的关联着色、圈与完全二部图的笛卡尔积图的关联着色、完全图与完全二部图的笛卡尔积图的关联着色,根据笛卡尔积图的特点,采用穷染的方法确定了其中部分图类的关联色数,从而验证了关联着色猜想在这些笛卡尔积图类中是正确的。     

整数距离图G（Dm，3）的点线性荫度

整数距离图G（D）以全体整数为顶点集，顶点u，v相邻当且仅当│u-v│∈D，其中D是一个正整数集．对于m〉3，设Dm，3={1，2，…，m│＼│3}，本文得到了G（Dm,3）的点线性荫度的上界和下界并决定出了它在某些较小的m上的确切值．     

图中点对偶的几个着色定理及算法

探讨了简单图Ｇ＝（Ｎ，Ｅ）中不邻接点的着色问题，给出连通的简单图中，点对偶在ｒ（Ｇ）＝ｋ）着色中为同色和异色的性质，色数的存在区间等，提出了求简单图色数的一种较有效的算法。     

点可区别边色数和点可区别全色数的两个上界

应用概率方法中的第一矩量原理和Markov不等式,证明了对于最大度为Δ的n阶图G,当Δ≥2时,其点可区别的边色数χv′d（G）≤nΔ（n-1）,当n≥3,Δ≥1时,其点可区别的全色数χvt（G）≤2 nΔ（n-1）.     

两类徨图的边色数

通过巧妙的构图，用图论的方法，完全确定了循环图Ｃｎ〈１，ｋ〉和Ｃｎ〈１，ｋ，ｎ／２〉的边色数。     

整数距离图G(Dm,3)的点线性荫度

整数距离图G(D)以全体整数为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集.对于m＞3,设Dm,3={1,2,…,m}＼{3},本文得到了G(Dm,3)的点线性荫度的上界和下界并决定出了它在某些较小的m上的确切值.     

k色图的连通性

研究和讨论了图的顶点着色问题中k色图的连通性,利用归纳与迭代的方法证明了对于任何k色连通图G,存在顶点V(G)的一个着色X1,X2,…,Xk,使得对该着色类中任意顶点集Xi所诱导出的Gk的子图Gk(Xi)都是连通的.从而证明了Chen,Schelp和Shreve关于k色图的连通性的一个推测.最后将所得的结论作了进一步推广.     

若干色临界图和色极小图的构造

一个图Ｇ,若对任意的顶点Ｖ（边ｅ）,Ｘ（Ｇ－ｖ）＜Ｘ（Ｇ）（Ｘ（Ｇ－ｅ）＜Ｘ（Ｇ））,则称Ｇ是色临界的（色极小的）．给出了色临界图和色极小图的几个构造方法,并探讨了这些构造方法的性质。