Tutte定理的几个推论

本文得到了Ｔｕｔｔｅ定理的几个推论，这几个推论在计算某些图的色多项式时是有用的。     

（v,e）——图正常2一着色的最大数目与极图

设Ｐ（Ｇ，λ）表示图Ｇ的色多项式。给定正整数ｖ，ｅ和λ，设ｆ（ｖ，ｅ，λ）＝ｍａｘ（Ｐ（Ｇ，λ），Ｇ是个（ｖ，ｅ）－ｌｔｕ ）。若一个（ｖ，ｅ）－图Ｇ使得Ｐ（Ｇ，λ）＝ｆ（ｖ，ｅ，λ），则称Ｇ是个λ－极图。本文指出文「２」给出的２－极图族是不完全的，并得到２－级图的完全族。     

完美全图的色多项式

设G(V,E)是简单图,而 V(T(G))=V(G)∪E(G), E(T(G))={yz|y、z∈V(T(G)),y、z在G中相邻或相关联}.称T(C)为G(V,E)的全图。若对G的每一导出子图H,其色数X(C)、团数ω(G)满足X(G)=ω(G),则称G是完美的。本文给出了完美全图的色多项式。     

n阶q-树的三次整子图色性的注记(上)

Chao等,韩伯棠和Thomas Wanner分别仅用色多项式表征了q-树和q-树的(一次)整子图;刘象武等又在参考文献中表征了当最小度δ(G)≠q-3时,q-树的二次整子图的色性。本文证明了n阶q-树的三次整子图G的色多项式为：P(G;λ)=λ(λ-1)…(λ-q 1)^4(λ-q)^n-q-3且G为q 1色图,色分划数为8;反之,在G的一个q 1着色下,若恰有一个二色子图不连通,则G是n阶q-树的三次整子图。     

n阶q-树的三次整子图色性的注记(下)

Chao等,韩伯棠和Thomas Wanner分别仅用色多项式表征了q-树和q-树的(一次)整子图;刘象武等又表征了当最小度Δ(G)≠q-3时,q-树的二次整子图的色性．本文证明了n阶q-树的三次整子图G的色多项式为：P(G;λ)=λ(λ-1)…(λ-q 1)^4(λ-q)^n-q-3且G为q 1色图,色分划数为8;反之,在G的一个q 1着色下,若恰有一个二色子图不连通,则G是n阶q-树的三次整子图。     

图的双变量色多项式比较研究

对图论的一些著名的双变量色多项式进行比较研究,对Tutte,Potts,Matching和Dohmen多项式,从定义、表达式的关系以及性质进行比较.特别地,对Tutte多项式的减-缩边公式,给出严格证明;对其余3种,则补充了它们各自的减-缩边公式以及证明.同时,由这些减-缩边公式得出它们各自一些特殊图的色多项式的具体计算公式,显示了减-缩边公式在简化计算方面的应用.     

关于（k,d）—图的性质

（ｋ，ｄ）－图是Ａ，Ｖｉｎｃｅ在１９８８年研究图的星着色时给出的定义，（ｋ，ｄ）－图在研究图的星着色中起着非常重要的作用，本文给出了一些（ｋ，ｄ）－图的性质，并根据这些性质构造了一个４－正则，４－连通的平面图，其星色数为４。     

一类广义树的色性

本文证明了图G是树序列为{1，p，1，q-4个…1，2，2，r}的广义树的充要条件是G的色多项式为P(G；λ)=λ(λ-1)^p(λ-2)…(λ-q 2)^2(λ-q 1)^2(λ-q)^r，这里q=4.5。     

线性束理论和环链的Kauffman多项式

利用Ｔｅｍｐｅｒｌｅｙ－Ｌｉｅｂ代数讨论了环链图形成的Ｚ（Ａ，Ａ＾－１）－模的性质，并给出了环链的Ｋａｕｆｆｍａｎ多项式的计算。     

N≤4的哈斯图色性

本文根据色性将n≤4的哈斯图进行了分类,并给出哈斯图与无向简单图比较图表.     

|V(G)|≤4图中色性相同图的性质

将图从|V(G)|=1开始通过重新梳理所有简单图的色性,找到一些色性相同的图.并将|V(G)|=1到|V(G)|=4的简单图色性,按其互补的形式汇总成表格.     

与5-树二次整子图色多项式前三高次项系数都相同的第三类图

本文给出了与5-树二次整子图色多项式前三高次项系数都相同的第三类图,从而说明了与5-树二次整子图色分划数、顶点数、边数和三角形数都相同的图,除它本身和加点5-树外,还有别的图。     

C_mP_n和GP_n的全色数

图染色的基本问题是确定各种染色法的色数.图G和H的直积图GH是一类很重要的图积,给出了直积图CmPn的全染色的方法,得到其全色数χ′′(CmPn)={4n2 5n=≥3,并进一步推广到图GPn的正常全染色,得到其全色数χ′′(GPn)={△(G)+2n=2 2△(G)+1n≥3.     

C5关联图的圆染色

构造了一个特殊图I(C5), 证明了I(C5)的圆色数是10/3,研究了I(C5)的子图的圆色数,证明了I(C5)没有子图的圆色数是8/3.     

图K_n\E(F_3)(n=17,19)的点可区别全染色

一个图的全染色被称为点可区别的即对任意2个点的相关联元素及其本身所染颜色构成的集合不同.给出了图Kn\E(F3)(n=17,19)的一种点可区别全染色方法,利用此方法得出了图Kn\E(F3)(n=17,19)的点可区别全色数.     

蛛形图的D(3)-点可区别的边染色

蛛形图是一个重要的网络拓扑结构,研究它的染色对于网络权的分配有重要的指导作用.利用穷举法和组合分析法讨论了蛛形图的D(3)-点可区别的边染色,得到了蛛形图的D(3)-点可区别的边色数.     

C_mC_n的邻点可区别全色数

给出直积图CmCn的一个邻点可区别全染色,得到其邻点可区别全色数χat(CmCn)=6.     

中间图的邻点可区别全染色

设G是简单连通图，G的庀．正常全染色f称为是邻点可区别的，如果对G的任意相邻的两顶点，其点的颜色及关联边的颜色构成的集合不同，称f为G的k-邻点可区别全染色．这样的后中最小者称为G的邻点可区别全色数．本文考虑了图的中间图的邻点可区别全色数，并确定了路、圈、星图和扇图的中间图的邻点可区别全色数．