论文摘要
本文中考虑的图都是简单图。分别用V（G），E（G），|G|，Δ（G），δ（G）表示图G的点集合，边集合，点的个数，最大度和最小度。对x∈V（G），用NG（x）表示在G中与点x相邻的所有点的集合，用dG（x）表示点x的度。度为k的点称为k-度点。设G是一个图，G的一个k-着色f是从V（G）到1，2，…，k的一个映射。对于图G的给定的k-着色，Vi表示G中所有染i色的顶点集（1≤i≤k），<Vi>表示G中由Vi导出的子图，若对于任意的i（1≤i≤k），都有<Vi>是森林，则称f是一个k-树着色。使G有k-树着色的最小数k称为图G的点荫度，记为va（G）。若对于任意的i（1≤i≤k），都有<Vi>的每个连通分支都是路，则称f是一个k-路着色。使得图G有k-路着色的最小正整数k称为图G的点线性荫度，记为vla（G）。显然va（G）≤vla（G）≤x（G）。任意两点u，v∈V（G），它们之间的距离为连接这两个点的最短路的长度，用distG（u，v）表示。图G的平方图G2是以V（G）作为它的点集，两个点u，v在G2中相邻当且仅当1≤distG（u，v）≤2。对于平面图，显然有下面著名的四色定理。定理1[32][33][34]若图C是平面图，则x（G）≤4。对于平面图的平方图的点着色，Wegner[35]在1977年提出了如下猜想：猜想2[35]若图G是平面图，它的最大度为Δ，则[21][22][23][24]中部分的证明了这个猜想。本文中我们主要考虑平方图的点荫度和点线性荫度。本论文的第一节主要介绍了平方图及点荫度和点线性荫度的基本概念和一些背景知识，第二，三，四，五节依次讨论了树图，外平面图，K4 minor free图，平面图的平方图的点荫度和点线性荫度，第六节讨论了两个完全图的笛卡儿乘积图的点荫度和点线性荫度。本文的主要结果如下：1．T是一棵树，它的最大度为Δ，那么2．G是一个外平面图，它的最大度Δ≥6，则3．图G为K4 minor free图，它的最大度为Δ，则4．图G是一个平面图，它的最大度为Δ，那么va（G2）≤Δ+13。5．当m=n=2k（k∈Z+）时，va（km×kn）=vla（km×kn）=k+1；其它情况下，va（km×kn）=vla（km×kn）=max{[m／2]，[n／2]}。