高度不正则图的全着色

图Ｇ的正常ｋ全着色是指用ｋ种颜色对Ｇ的点和边着色，使相邻或相关联的元素（点或边）着不同色。其中最小的ｋ称为Ｇ的全色数，记为χＴ（Ｇ）。设Ｇ是一个简单图，υ是Ｇ的任意一个顶点，若与υ相邻的顶点的度互不相同，则称Ｇ为高度不正则图。对高度不正则图Ｇ，文中证明了χＴ（Ｇ）＝Δ（Ｇ）＋１，同时也给出了着色的算法，其中Δ（Ｇ）为Ｇ的最大度数且Δ（Ｇ）≥２。

高度不正则图的两个结果

本文证明了阶不小于4的连通图和补图均为高度不正则图当且仅当图为4阶的路,同时证明了对于高度不正则图,其边色数等于最大度。

关于几类图的L(3,2,1)-标号问题

图G的L(2 ,1 )_标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则|f(x) -f(y) |≥ 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) |≥ 1 .图G的L(2 ,1 )_标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L(2 ,1 )_标号中的最小数k.该文将L(2 ,1 )_标号问题推广到更一般的情形即L(3,2 ,1 )_标号问题 ,并得出了Kneser图、高度不正则图、Halin图的λ3(G)

高度不正则树的存在性

本文证明了对不等于3,5,6,7,11,12.13的任意正整数 n,存在 n 阶高度不正则树,同时给出它的最大度d 的上界 d_(max)=[log_z n]和下界 d^(min)=0(n=1).或1(n=2),或2(n=4).或3(n=2~3+6r+s,r=0,1,2,3,….s=0,1,2),或4(n>16且 n≠2~3+6r+s),并证明对任意正整数 k∈[d_(min),d_(max)],存在最大度为 k 的 n 阶高度不正则树.

Unretractivity and End-Regularity of a Graph

In this paper, a relationship among unretractivity, E-H-unretractivity andend-regularity of a graph is described.