侯永艷 岳秋菊

【摘 要】聯(lián)圖的點染色問題文獻中沒有做研究，文中研究了的點染色問題，得到了點色數(shù)。研究結(jié)論希望能為包裝和印染業(yè)中顏料的正確合理使用提供理論指導(dǎo)。

【關(guān)鍵詞】聯(lián)圖 點染色 點色數(shù) 聯(lián)圖

中圖分類號：O157 ；TP311

引言

近幾年來我們提出了圖的點染色概念，但對聯(lián)圖的點染色問題所有文獻均未涉及，本文研究了聯(lián)圖的點染色，得到了的點色數(shù)。相關(guān)術(shù)語、記號可參見文獻[1-3]。

1 主要結(jié)論及其證明

定義：設(shè)圖是一個簡單圖，若滿足下面的條件，記為。滿足：

=；

文中討論了圖的點染色方案，得到了圖的點色數(shù)。

定理：對于圖有：

；

證明：情形1：當時，令的染色法為：

；；；…；；；；；…；；； ；；…；；；；；…；；；；；；可見是的。

情形2：當時，令的染色法為：

用情形1的染色方案將染色完畢。再進行如下的染色：

；；；…；；；；；…；；；；可見是的。

情形3：當時，令的染色法為：

用情形2的染色方案將染色完畢。再進行如下的染色：

；；；…；；；；；…；； ；；可見是的。

一般的可以用如下的染色方案對任意的進行點染色：；；；；；

可見對于任意的都存在。綜上所述結(jié)論成立。

結(jié)語

在印染行業(yè)和包裝行業(yè)出現(xiàn)該聯(lián)圖且按點染色方法染色時，可以按本文所研究的染色方案進行有效染色。希望本文所研究內(nèi)容對印染和包裝工業(yè)中顏料的合理使用提供理論指導(dǎo)。

參考文獻

[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.