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

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

两类联图的全着色

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

图的全谐调着色数

图的全谐调着色数表示为Th(G)是相邻的点与边着不同颜色 ,且任何两个不同的边上有不同的三元颜色组的最小着色数。本文给出了关于图的全谐调着色数的各种定理     

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

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

图的分散着色和分数色数

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

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

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

图的色数问题研究（续）

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

自补图的独立数与覆盖数

主要讨论了自补图的边独立数和边覆盖数，给出了点独立数的严格上、下界：Ｐ／ｘ（Ｇ）≤α（Ｇ）≤「Ｐ＋１／２」，其中ｘ（Ｇ）是Ｇ的点色数，分析并证明了点独立数取得上、下界的自补图的存在性。     

LPT算法的两个近似界估计

本文讨论带机器准备时间的平行机排序问题．由于它是ＮＰ－ｈａｒｄ的，我们讨论近似算法ＬＰＴ，研究它在使ｍａｋｅｓｐａｎ达到最小和ｍｉｎｉｍｕｍｃｏｍｐｌｅｔｉｏｎｔｉｍｅ达到最大两个目标下的近似程度．     

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

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

带准备时间的平行机排序的LPT算法

本文考虑带准备时间的平行机排序问题，讨论在使最早机器完工时间达到最大目标下的优化问题．这是ＮＰ－ｈａｒｄ问题，本文证明ＬＰＴ排序解至少是最优解的倍．     

关于外平面图的局部调和着色

详细讨论了外平面图Ｇ（Ｖ，Ｅ）的ＬＨＣ，并证明了对于图Ｇ，若Δ≥５则满足ＸＬＨＣ（Ｇ）＝Δ ＋１；从而证明了对该类图Ｇ，全着色猜想成立，使得文献为本文的一个特列。     

应用思维进化计算求解顶点着色问题

应用思维进化计算求解顶点着色问题，给出求解给定图的色数、最小着色的算法。介绍了顶点着色问题的编码与解码方法、特征、信息矩阵的概念，从而应用思维进化计算的趋同和异化求解该问题。实验结果表明该算法是求解顶点着色问题的一种新的有效算法。     

维数不超过7的超立方体三次幂的可区别数

根据n维超立方体Hn及其p次幂Hn^p的结构特性,结合其顶点间距离与海明距离关系来确定其顶点坐标的性质,采用“脊”的技术和顶点着色的方法,对维数不超过7的超立方体三次幂的可区别数进行了研究。通过适当地选取顶点得到了H3^3的可区别数为8,H4^3的可区别数为5,H6^3和H7^3的可区别数都为2,及H5^3可区别数的一个上界为3。     

两类齿轮图的分数色数

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

两类距离图的分式色数和点色数

分式色数和点色数是图的两个重要参数。本文在文献[1]的基础上给出了两类距离图G（Z,Dm,k,k 1)与G（Z,Dm,k,k 1,k 2）的分式色数和点色数。     

求顶点着色问题的一种新方法

给出了图的着色问题的一种新方法，即运用置换相似变换(置换行和相应的列)得到图G的顶点集I/(G)的一种分划(V1，V2，…，Vn)，从而得出图的色数及最小着色等一系列相关问题．     

最大度为5的非正则图的无圈着色

图G的无圈着色是指正常的顶点着色,同时图中任意的圈均不着双色。换句话说,图G的无圈着色是指G的正常顶点着色并且由任意两类颜色导出的子图G'为森林。图G的无圈色数是指在G的所有无圈着色中使用色数的最小者,这里用a(G)表示。证明了最大度为5的非正则图的无圈色数最多为8,并由此推出含有割边或割点的五正则图均可以用8种颜色进行无圈着色。     

独立数,连通度及r—消去图

改进了关于ｒ－因子的结果，给出了一个图是ｒ－消去图的充分条件，并且用例子说明此结果是最好的可能。结果如下：定理Ｉ设ｒ≥１是奇数，Ｇ是一简单图，且Ｖ（Ｇ）为偶数，如果ｋ（Ｇ）〉（ｒ＋１）＾２／２，且（ｒ＋１）＾２ａ（Ｇ）〈４ｒｋ（Ｇ），那么Ｇ为ｒ－消去图。定理Ⅱ设ｒ≥２为偶数，Ｇ是一简单图，如果ｋ（Ｇ）〉ｒ（ｒ＋２）／２，且（ｒ＋２）ａ（Ｇ）〈４ｋ（Ｇ），则Ｇ为ｒ－消去图。     

图的色数问题研究

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