多重图的边着色研究

郑学谦， 乔晓云

（山西大学商务学院，山西 太原 030031）

0 引 言

图论是数学的一个分支，是近年来发展迅速而又应用广泛的一门新兴学科。图的着色问题［1］是图论中十分活跃的研究课题，有着深刻而丰富的理论结果和广泛的实际应用，诸如时间表问题、排课表问题、存储问题等，其理论和方法在离散数学中占有重要地位。Ving［2－3］等很早就研究了多重图的色数问题；唐明元［4］研究了满足2色P4条件完全图的边着色；王俊梅［5］研究了四类圈树的连续边着色；张鑫［6］等研究了环形图的边着色。在此基础上，文中定义了多重图的R（k，n：p）－边着色，并利用正交拉丁方和矩阵的乘法证明了当m≡0（mod2）时，图是R（2，m：4）－边着色图。

1 基本概念

定义1［7］M称为r－多重完全图，如果M的任意两个不同的顶点都有r条边。n阶的r－多重完全图记为

定义2［7］多重图m边着色指的是每一条边着给定的m种颜色中的一种，任意两个顶点之间的边着不同颜色。

定义4［8］设n为正整数，S＝｛0，1，2，…，n－1｝，使得S中的n个元素中的每一个均在每一行出现一次（从而恰好一次）且在每一列出现一次，即每一行和每一列都是S的元素的一个排列，这样组成的n×n矩阵A称为n阶拉丁方。

2 主要结果

证明 第1步：利用模n的加法运算得到偶数阶对称拉丁方A2，A4，A6，…，A2n，…

第2步：利用算法构造对角线元素全是0偶阶对称拉丁方。

算法如下：

1）把每一行（除去第一行和最后一行）中要放到最后一列的数找出。这个数的位置根据如下规律确定：

2）把拉丁方A2n中对角线的元素aii和由1）找到的数提出，这行的其它数将向左移1位。

3）将矩阵对角线上的元素放在该行对角线的位置上，将剩下的另一个数放在最后一列。

4）最后一行元素由对称所得。

第3步：将矩阵A2与A2n作运算得出图的边标号，其中（i，j）表示vivj二重边的标号。

，…

…

［1］ Bondy J A，Murty U S R.Graph theory with applications［M］.New York：The Macmillan Press Ltd.，1976.

［2］ Ving V.The chromatic class of multigraph［J］.Cybernetics，1965（1）：32－41.

［3］ Steffen E.A refinement of vings theorem［J］.Cybernetics，2000（1）：289－291.

［4］ 唐明元.满足5色K4条件完全图的边着色［J］.上海师范大学学报：自然科学版，2003（3）：21－25.

［5］ 王俊梅.四类圈树的连续边着色［J］.太原师范学院学报：自然科学版，2012（4）：4－6.

［6］ Zhang Xin，Liu Guizhen.On edge colorings of 1－toroidal graphs［J］.数学学报：英文版，2013（7）：1421－1428.

［7］ 邵泽辉.Ramsey理论中图的构造与计算［D］.武汉：华中科技大学，2008.

［8］ 冯舜玺.组合数学［M］.北京：机械工业出版社，2005.