关于图的点强全着色

图G(V,E)的一正常k-全着色σ称为G(V,E)的一个k-点强全着色,当且仅当ν∈V(G),N[ν]中的元素着不同颜色,其中N[ν]={u|νu∈E(G)}∪{ν}。并且χνsT(G)=min{k|存在G的一个k-点强全着色}称为G(V,E)的点强全色数。本文得到了一些特殊图的点强全色数χνsT(G),并提出猜想:对于简单图G,有k(G)≤χνsT(G)≤k(G) 1,这里k(G)是文中给出的一个新的参数。     

3—正则Halin图的全色数

研究了△（G）=3时Halin图的全色数,证明了：(i)对于3－正则的Halin图G,有4≤xT(G)≤5;(ii）若将3－正则Halin图每边剖分一次,由于对剖分图M^*有xT(M^*)＝4,这里△（G）表示图G的最大度数,xT(G)表示图的G的全色数。     

关于全着色Ramsey数

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

n阶4正则简单图不一定含n阶3正则子图

文章通过构造一个反例说明偶数阶4正则简单图中不一定含完美匹配,从而证明n阶4正则简单图不一定含n阶3正则子图。     

关于一些图的Double图的全色数

图的全染色是指对顶点和边同时染色,使得相邻或相关联的元素染不同的颜色,其所用最少染色数称为全色数,记为ΧT（G）.本文得到了星、扇和轮的Double图的全色数.     

路的笛卡尔乘积图的邻点可区别全染色

一个正常的全染色满足相邻顶点的顶点及其关联边所用的色集合不同时,称为邻点可区别全染色,其所用的最少的颜色数称为顶点可区别全色数。刻画了路与路的笛卡尔乘积图的邻点可区别全色数。     

关于若干倍图的第一类弱全染色

对简单图G(V,E),f是从V(G)U E(G)到{1,2,…,k}的映射,k是自然数,如果对任意的uv∈E(G),有f(u)≠f(u),对任意的uv,uw ∈E (G),u≠w,有f(uv)≠,f(uw),则称f为图G的一个第一类弱全染色.最小的k称为G的第一类弱全色数.给出了路、圈、星、扇、轮、完全图的倍图的第一类弱全色数.     

完全图的点可区别V-全染色

根据图的点可区别全染色的概念及其染色方法,讨论了图的点可区别V-全染色,给出了完全图Kn的点可区别V-全色数的结论及其证明,为进一步探讨其他简单图的点可区别V-全染色提供了理论证据,丰富了图的点可区别V-全染色的结果.     

星与扇联图的邻点可区别全染色

把星Sm中的每一个点与扇Fn中的每一个点相连,得到星与扇的联图,记为SmVFn．本文给出了SmVFn的邻点可区别全色数．     

星的细分图的IC-着色

研究了星的细分图的IC-着色问题,改进了星的细分图的IC-指数的下界,并且得到了两类图的IC-指数的一个下界。     

Sm V Sn的全色数

本文给出m 1阶星和n l阶星的联图的全色数的结果:Xt(SmVSn)={△(SmVSn) 21,当m=n=1;/△(SmVSn) 1,否则     

图T1,1,m与Q(3,n)中有路因子的充分必要条件及T1,1,m的匹配等价类

如果一个图的匹配多项式可以被一个路的匹配多项式整除，我们就说这路是该图的一个路因子，路因子在刻画图的匹配等价类，研究匹配唯一性方面有很重要的作用．得到了T1，1，m与Q（3，n）中有路因子的充分必要条件．并且给出了T1，1，m当m≠4k（k为正整数）时的匹配等价图类。     

3＿线图的完美性

本文给出了3＿线图含有奇洞的充要条件,从而使3＿线图的完美图猜想得到彻底解决,同时,本文还给出完美3＿线圈是k点染色的充要条件及3＿线图是连通的充要条件等一些结论。     

Pm×Pn的全色数

给出了图的一种染色方法,并证明了该染色为正常全染色,从而得到了Pm×Pn的全色数：Xt（Pm×Pn）={4 m=2,n≥2或m≥2,n=2 5m〉2,n〉2．此结果尚未见其它文献报道．     

联图Cn ∨ Kn的全色数

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

联图CnVKn的全色数

研究了联图CnVKn=2n的全色数,证明了当n〉5时,金色数XT（CnVKn）=2n,从而证明了CnVKn．满足全着色猜想.     

蛛形图的全染色和星全染色

蛛形图是一个重要的网络拓扑结构,研究它的染色对于网络权的分配有重要的指导作用。利用穷举法和组合分析法讨论了蛛形图的全染色和星全染色,得到了蛛形图的全色数和星全色数,丰富了图染色的内容。     

Pm×Pn的全色数

给出了图的一种染色方法,并证明了该染色为正常全染色,从而得到了Pm×Pn的全色数:χt(Pm×Pn)=54!mm>=22,,nn>≥22或m≥2,n=2.此结果尚未见其它文献报道.     

图的邻点强可区别全色数

图的染色是图论的主要内容之一,它在通讯线路的设计,算法设计与分析以及理论计算机等方面有广泛的应用。如何确定一种图染色法的色数大小,是图染色研究的主要问题。概率方法是一种研究图染色的新方法,它主要用来估计图染色法的色数的上界。利用概率方法研究了图的邻点强可区别的全染色,得到了图的邻点强可区别的全染色的一个上界。     

基于图着色算法的考试时间安排系统的设计与实现

广播电视大学的考试管理机制不同于普通高等学校,如何解决考生的＂补考＂和＂正考＂的时间冲突是考试安排中一项复杂的工作。本文主要研究利用改进的图着色算法处理考试时间安排问题,通过分析考试安排问题的实际情况,基于所给出的算法,设计考试时间安排系统。实验测试表明,该系统具有良好的可行性、实用性和优越性。