若干合成图的星全染色＊

王晓琦 田双亮

（西北民族大学数学与计算机科学学院 兰州 730030）

0 引 言

本文所考虑的图G均为有限无向简单图，用V（G），E（G）分别表示图G的点和边的集合.并用Δ（G）表示G的最大度.

定义1［1］简单图G和H 的合成图是指具有顶点集V（G）×V（H）的简单图G［H］，它的顶点（u，v）和另一个顶点（u′，v′）相邻当且仅当或者uu′∈E（G），或者u＝u′且vv′∈E（H）.

合成图G［H］也可看成是若干个同构于H的不相交图关于G的等广义联图［2］.特殊地，当G为n阶完全图Kn，合成图Kn［H］也可称为n阶完全图Kn与H 的等多重联图［3］.

定义2 图G的k－全染色是从V（G）∪E（G）到S＝｛1，2，…，k｝的一个映射σ，使得G 中没有相邻顶点或边具有相同的像，且每个顶点与其关联边有不同的像.使G存在k－全染色的最小k值称为G的全色数，记为χT（G）.

定义3 图G的一个k－全染色σ被称为k－星全染色，如果图G中任意长为2的路的顶点和边染不同颜色.即G中任意星上的顶点与边染不同的颜色.使G存在k－星全染色的最小的k值称为G的星全色数，记为χst（G）.

由定义3，容易得到以下引理：

引理1 对任意n阶简单图G，n≥3，有2Δ（G）＋1≤χst（G）≤n＋χ′（G）.式中：χ′（G）为G的边色数.

引理2 对G的任意子图H，有χst（H）≤χst（G）.

引理3 若G的直径D（G）≤2，则在G的任一星全染色中，G的不同顶点必染不同的颜色.

在后面的讨论中，需用到以下引理：

引理4 偶图G的边色数等于Δ（G）.

文献［2］研究了一些等广义联图（或合成图）的Mycielski图的星全染色，文献［4－7］研究了完全图与完全多部图的Mycielski图，以及轮，扇与路的广义Mycielski图的星全染色.本文将研究n＋1阶轮，扇，星与m阶简单图的合成图的星全染色.文中未加说明的术语及符号可参见文献［1］和［4］.

1 主要结果及其证明

设简单图G与H 的顶点集分……