联图的r（2）点染色

侯永艳 岳秋菊

【摘 要】联图的点染色问题文献中没有做研究，文中研究了的点染色问题，得到了点色数。研究结论希望能为包裝和印染业中颜料的正确合理使用提供理论指导。

【关键词】联图 点染色 点色数 联图

中图分类号：O157 ；TP311

引言

近几年来我们提出了图的点染色概念，但对联图的点染色问题所有文献均未涉及，本文研究了联图的点染色，得到了的点色数。相关术语、记号可参见文献[1-3]。

1 主要结论及其证明

定义：设图是一个简单图，若满足下面的条件，记为。满足：

=；

文中讨论了图的点染色方案，得到了图的点色数。

定理：对于图有：

；

证明：情形1：当时，令的染色法为：

；；；…；；；；；…；；； ；；…；；；；；…；；；；；；可见是的。

情形2：当时，令的染色法为：

用情形1的染色方案将染色完毕。再进行如下的染色：

；；；…；；；；；…；；；；可见是的。

情形3：当时，令的染色法为：

用情形2的染色方案将染色完毕。再进行如下的染色：

；；；…；；；；；…；； ；；可见是的。

一般的可以用如下的染色方案对任意的进行点染色：；；；；；

可见对于任意的都存在。综上所述结论成立。

结语

在印染行业和包装行业出现该联图且按点染色方法染色时，可以按本文所研究的染色方案进行有效染色。希望本文所研究内容对印染和包装工业中颜料的合理使用提供理论指导。

参考文献

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

[2]Hansen P，Marcotte O，Editors.Graph Coloring and Application[M].AMS providence， Rhode Island USA，1999.

[3]Burris A C and Schelp R H.Vertex-distinguishing Proper Edge-colorings[J]. Journal of Graph Theory，1997，26：73-82.