完全二部图全着色的构造

利用全着色矩阵给出完全二部图全着色的构造,该构造可以方便快捷对完全二部图进行全着色.     

n阶完全图全着色的构造及其推广

引进了图的全着色矩阵的概念,从而给出了n阶完全图全着色的构造,并推广到任意n阶图G的最大度Δ(G)=n-1的情形,给出了与猜想等价的命题·     

几个特殊图的全着色

设G是一个图,G的全着色是一个映射π:V(G)YE(G)C,使得相关联或相邻的元素着不同色;G的所有全着色中,使得色数的最小者,称为G的全色数,记为χT(G);得到了几个特殊图的全色数     

几类含圈图的全着色

对于图G=（V，E），一个正常全着色就是从VUE到一个整数集的映射，使VUE中的任意两个相邻或相关联的元素都着不同的颜色，图G=（V，E）的全色数xτ（G）定义为xT（G）=min{k｜存在G的一个正常k-全着急}，本文对一类特殊图-含圈图的全着色给出了几个定理，验证了全着色猜想。     

一些图的全着色计数

对给定图Ｇ,用Ｎ（Ｇ）代表使用ＸＴ（Ｇ）（指图Ｇ的全色数）种色对Ｇ的所有不同的正常全着色的数目．导出了路、星、长为３Ｋ的圈以及树的Ｎ（Ｇ）的计数公式     

关于奇阶同阶图的联图的全着色

图Ｇ的全色数ｘＴ（Ｇ）是使得ＶＥ９Ｇ）中相邻接或相关联的元素均着不同颜色的最少颜色数，证明了：如果ｖ（Ｇ）＝ｖ（Ｈ），存在ｖ∈Ｖ（Ｇ），Ｖ‘∈Ｖ（Ｈ）使得Ｇ＾ｃ－ｖ和Ｃ－ｖ’都含有完美对集且Δ（Ｇ）＝Δ（Ｈ）并存在ｅ∈Ｅ（Ｇ－ｖ），ｅ‘∈Ｅ（Ｈ－ｖ’），使得Ｇ－ｅ和Ｈ－ｅ‘都是第一类图，或ΔＧ）〈（Ｈ）且存在ｅ∈Ｅ（Ｈ－ｖ’）使得Ｈ－ｅ‘是第一类图，则ｘＴ（ＧＶＨ）≤Δ（ＧＶＨ）＋２。     

轮形图的全着色

图G(超图H)的全着色是指同时给图中的顶点和边进行着色,使相关联或相邻的元素间着不同的颜色,而使用的最少的颜色数就称为全色数,记为xT(G)(xT(H)).超图的全着色又可以分成弱全着色和强全着色2种情况.本文主要讨论超图中轮形图W(v)的全着色性质,并得到具体的强全色数和弱全色数,xWT(W(v))=△+1,xST(...     

全着色边临界图的一个注记

研究了全着色边临界图的结构，证明了对于△≥5的全着色边临界图G（V，E），若u∈V（G），d（u）=3，uvi∈E（G）（i=1，2，3），则△-1≤d（vi）≤△．     

区间图和强弦图的全着色及最优算法

证明对于任意区间图和强弦图－全着色猜想成立，并且给出了区间图和强弦图的最优线性地，其算法复杂度仅为Ｏ（Ｖ＋Ｅ）。     

高度图的全色数

证明了：如果图G的最大度顶点数r(G）满足r(G)≥|V（G）|-△（G）-1,且δ（G） 2△（G）≥5/2|V（G）| 3/2,则G的全色数xT(G)=△（G） 1。     

2－退化图的全色数

对任意简单图Ｇ，Δ（Ｇ）和ＸＴ（Ｇ）分别表示Ｇ的最大度和全色数．证明了当Δ（Ｇ）≥４时，２－退化图Ｇ的全色数ＸＴ（Ｇ）＝Δ（Ｇ）＋１．     

图的D(b)-点强可区别的全染色

提出了图的D(b)-点强可区别的全染色的概念并给出了几个基本定理,通过穷举法和组合分析法研究了b=2时,路图的具体染色,最后提出了一个猜想.     

齿轮图的邻点强可区别的全染色

利用穷举法和组合分析法讨论了齿轮图Wn(n≥3且n≠4)的邻点强可区别的全染色,通过构造具体染色得到了齿轮图Wn(n≥3且n≠4)的邻点强可区别的全色数。     

单圈图的全图谱半径

利用移接变形的方法研究单圈图及其全图的谱半径,给出这2类图的谱半径达到上下界的极图.     

合成图的全着色

对于任意简单图G,Δ(G)和t(G)分别表示G的最大度和全色数.本文证明了如果G的全色数满足t(G)≤Δ(G)+2,则合成图G[(?)_m]和K_n[G]的全色数满足t(G[(?)_m])≤Δ(G[(?)_m])+2,t(K_n[G])≤Δ(K_n[G])+2。