关于图的邻点可区别全染色

提出了图的邻点可区别全染色的概念, 给出了圈、完全图、完全二部图、扇、轮和树的邻点可区别全色数.  

图的距离不大于β的任意两点可区别的边染色

本文提出了图的距离不大于β的任意两点可区别的边染色,即D(β)-点可区别的边染色(简记为D(β)-VDPEC)．并得到了一些特殊图类,如圈、完全图、完全二部图、扇、轮、树以及一些联图的D(β)-点可区别的边色数,文后提出了相关的猜想．  

图的距离不大于β的点可区别的全染色

提出了D (β)-点可区别全染色这一概念, 即对图G的一个正常全染色, 距离不大于β的任意两点有不同的色集, 其中, 每个点的色集由该点和其邻边的颜色所组成. 讨论了一些特殊图的距离不大于2的任意两点可区别全染色, 同时提出了一个猜想和一个未解决问题.  

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C，如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G），Vj′∈V（G′）且vivj∈E（G））那么，称D（C）是C的倍图，如果V（D（G））=V（C）∪V（G′），E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G），vj′∈V（G’）and vivj∈（G）），称D（C）是G的补倍图，这里G′是G的拷贝．本文研究了D（G）和D的色数，边色数，欧拉性，哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．  

正则图的邻强边染色和全染色

如果~$k$-\-正则图~$G$~不含~5-\-圈的分支, 则猜测~$\chi''_{\mathrm{as}}(G) = \chi_{\mathrm t}(G)$. 证明这个猜想对很多图类都成立, 例如: 第1类型图、 $2$-\-正则图、$3$-\-正则图、$(|V(G)|-2)$-\-正则图、二部图、完全等多部图、$k$-\-方体以及一些特殊的联图类等.  

若干联图的点可区别均匀边色数

k-正常边染色法f,若满足任两个不同点的关联边色集不同,则称f为G的k-点可区别边染色,简记为k-VDEC of G,并称最小的k为G的点可区别边色数;对k-VDEC若再满足任意两色的边数之差不超过1,则称f为G的点可区别均匀边染色,简记为k-VDEEC of G,并称最小的k为G的点可区别均匀边色数．本文得到了图等阶的路和路,路和圈,圈和圈的联图的点可区别均匀边色数．  

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

设 $G(V, E)$是阶数不小于~3 的简单连通图, $k$ 是自然数, $f$ 是从~$V(G)\cup E(G)$到 ~$\{1, 2, \dots, k\}$ 的映射, 满足: 对任意的 ~$uv\inE(G),f(u)\not= f(v), f(u)\not= f(uv)\not= f(v)$; 对任意的$uv,uw\in E(G)\,(v\neq w), f(uv)\neq f(uw)$; 对任意的$uv\in E(G), C(u)\neq C(v)$, 其中$C(u)=\{f(u)\}\cup \{f(v)|uv\in E(G)\}\cup \{f(uv)|uv\in E(G)\}$, 则称$f$是图$G$ 的一个邻点强可区别的全染色法. 简记作 $k$-AVSDTC, 且称 $ \chi_{\rm ast}(G)=\min\{k\mid G \textrm{ 的所有 }\ k\textrm{-AVSDTC}\} $ 为$G$ 的邻点强可区别的全色数. 得到了圈、完全图、完全二部图、树的邻点强可区别全色数.  

k-方体图邻点可区别全色数

本文证明k-方体图(k≥2)的邻点可区别的全色数为k+2.  

若干图的广义Mycielski图的边色数

设图G(V,E)为简单图,V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…,vn1,vn2,…,vnp}EMn(G))=E(G)∪vijv(i+1)kv0 jv0k∈E(G),1 j,k p,i=0,1,…,n-1称Mn(G)为G的n串广义M ycielsk i图,其中n为自然数,V(G)={v01,v02,…,v0p}.本文得到了路、圈、扇、轮、星图的广义M ycielsk i图的边色数.  

极大外平面图的邻强边色数

本文证明了对极大外平面图 G,Δ(G) χ′as(G)≤ Δ(G) +1,且 χ′as(G) =Δ(G) +1,当且仅当存在两个最大度点相邻 .其中Δ (G)、χ′as(G)分别表示图 G的最大度和邻强边色数 .