图PmvFn的全染色

刘君 任志国 赵传成 岳秋菊 蓝才会

（兰州城市学院 信息工程學院，甘肃 兰州 730070）

【摘 要】设有路和扇，则有

则称 为路和扇联图。本文对前述图进行了全染色并得到了全色数。图的染色在印刷、包装和储存等方面有较好的应用。

【关键词】路扇 联图 全染色 全色数

引言

定义设G（V，E）是阶至少为2的连通图，k是正整数， f是到的映射，如果

（1）对任意有

（2）对任意有

那么称为的正常全染色，简记为且称为的全色数

定义3设有路这和扇，则有

则称 为路和扇联图。

猜想1 如果G是简单图，那么

不等式左端是显然的，其中表示图G 的最大度。

本文研究了图的全染色，文中没加说明的术语、记号在[1]或[3]中找到。

主要结论

引理1[1][2]如果G是简单图，那么

（1）如果图只有一个最大度点，则：

（2）若图的最大度点均是割点，则：

其中表示G 的最大度

定理1 对图

证明：

情形1：当时，此时都是图的最大度点且相邻，由猜想1可知，为证明此时结论成立，只需证明图存在7-PTC。

设令

所以是，此时结论成立。

情形2：当时，此时都是图的最大度点且相邻，由猜想1可知，为证明此时结论成立，只需证明图存在。

设，令

所以是，此时结论成立。

情形3：当时，此时都是图的最大度点且相邻，由猜想1可知，为证明此时结论成立，只需证明图存在。

设，令

所以是，此时结论成立。

情形4：当时，此时是图的最大度点且只有一个，上引理1可知此时结论成立。

综合所述，结论成立。

结语

图的染色对于分布问题提供了一些理论依据，希望本文对印染行业、包装工业及储存运输行业能提供理论依据。

参考文献

[1]Bondy J A and MartyU S R，Graph Theory with Applications， The Macmillan Press Ltd， New York，1976.

[2]Zhongfu Zhang ，Jianfang Wang，A summary of the progress on total coloring of graphs，Adv Math，1992.

[3]PHansen，O Marcotte，Graph coloring and application AMS providence ，Rhode Islwnd USA ，1999.