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

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

关于图全着色的几个结果

引入了一种研究图全着色问题的新方法，即从考虑图中的圈出发研究全着色问题．运用该方法确定了一些图的全色数，并给出了图全色数的一个上界．     

轮形图的全着色

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

关于联图W_m∨P_n的均匀全染色

对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.就轮Wm与路Pn的联图Wm∨Pn,得到了在m,n不同取值情况下的均匀全色数.     

关于联图K_(1,m)∨P_n的全染色

就星与路的联图K1,m∨Pn,可得到在m,n不同取值情况下的全色数.     

一些图的全着色计数

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

关于联图的均匀全色数

对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数。本研究得到了G∨H的均匀全色数为它的阶,若满足以下条件之一:(1)当G的最大度等于它的阶减1,且G∨H的顶点数为奇数;(2)当G只有一个最大度点,且最大度等于它的阶减1,且H的最大度不大于它的阶减2,还得到了当G与H的最大度都分别不超过各自的阶减2时,G∨H的均匀全色数的一个上界。     

单圈图及其与完全图联图的全染色

研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性.     

若干联图的星全染色

图G的一个正常全染色如果满足G中任意路长为2的点和边着色均不相同,称为G的星全染色.图的全部k-星全染色中所用最少的颜色数称为图G的星全色数.文章研究了若干联图的星全色数.     

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

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

关于扇与完全等二部图的联图的全色数

研究m 1阶扇Fm与完全等二部图Kn,n的联图Fm∨Kn,n的全色数问题.借助于Vizing定理、若干引理及归纳总结的方法,得到Fm∨Kn,n的全色教最多为最大度加2,从而验证了对这类图全染色猜想的正确性.     

几类含圈图的全着色

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

关于全着色Ramsey数

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

等广义联图的Mycielski图的星全染色

研究了一些等广义联图的Mycielski图的星全染色,并得到了它们的星全色数。     

乘积图G×Pn和G×Cm的全着色

本文证明对乘积图G×Pn和G×Cm,若G∈C1T,则G×Pn∈C1T,G×C2m∈C1T和G×Cm∈C1TC2T;从而证明了乘积图Pr1×Pr2...×Pm∈C1r,Cr1×Cr2...×Cm∈C1T∪C2T.由此证明了对于这些图全着色猜想成立.     

若干联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射.如果uv∈E(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.称 f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到路和圈的联图的邻点可区别E-全色数.     

关于图的全染色和列表全染色方面的一些结果

证明了如下结果：一个简单连通图G的全色数和列表全色数都为△＋1，如果它存在一个支撑子树T使得△（G）≥6和△（G\E（T））≤2，或者△（G）≥4和△（G\E（T））≤1。     

等广义联图的Mycielski图的星全染色(英文)

研究了一些等广义联图的Mycielski图的星全染色,并得到了它们的星全色数。     

扇与轮的联图F_m ∨ W_n的均匀全色数

对一个正常的全染色满足各种颜色所染元素数（点或边）相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.就扇与轮的联图Fm ∨ Wn,得到了在m,n不同取值情况下的均匀全色数.     

几个特殊图的全着色

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