關于圖BBC染色的一些結果.pdf

1、本文討論的圖均為有限無向的簡單圖。
　　 對圖的染色研究是圖論的重要領域,2003年英國杜倫大學(Durhamuniversity)教授Hajo Broersma在第29屆國際計算機方面的圖理論研討會議上提出圖的BBC-染色概念.
　　 圖的BBC-染色是一種與網(wǎng)絡頻率分配問題相關的圖的染色問題.該染色中,圖是用來描述網(wǎng)絡信息傳輸系統(tǒng)的一種模型,其中頂點表示網(wǎng)絡傳輸站點(包括發(fā)射點,接收點,中轉點),若兩個網(wǎng)絡傳輸站點之

2、間的距離比較近,當其發(fā)射相同或相似頻率信息時,會產(chǎn)生相互干擾,則在圖中表示該兩個頂點相鄰.這個問題相當于對圖中的某些邊給出特定的限制,使得網(wǎng)絡頻率信息保持在可接受的水平,不至引起相互干擾.這就可以看作是著色問題:給定兩個有限圖G1,G2其中G1是圖G2的支撐子圖,用有限的顏色對G2進行著色,使得G1同時滿足G1,G2上的限制條件.根據(jù)以上說明,將定義概括為:設G(V,E)為簡單非平凡圖,S是G的生成子圖,(G,S)的一個BBC-k-染色

3、是指一個映射f:V(G)→{1,2,…k}.滿足:(1)(A)uv∈E(S)則｜f(u)-f(v)｜≥2;(2)(A)uv∈E(G)\E(S)則｜f(u)-f(v)｜≥1.那么稱f為(G,S)的一個BBC-k-染色,且稱BBC(G,S)=min{(G,S)有BBC-k-染色}為(G,S)的BBC-色數(shù).王維凡、卜月華等人討論了帶圍長、最大度限制圖的BBC-染色問題,得出:圖G連通,且mad(G)<5/2,則G中存在一個棵成樹T,使得BB

4、C(G,T)≤4.其中mad(G)=maxH()G{2｜E(H)｜/｜V(H)｜}.
　　 2009年周蘭,卜月華等人在文獻[20]中討論了Mycielski圖的BBC-染色問題.得到如下結論:圖G連通且｜V(G)｜≥2,則BBC(G,T)≤BBC(M(G),TM)≤BBC(G,T)+1.
　　 本文主要介紹了一些基本概念和已有結論,在本文第二章給出了關于帶有最大平均度限制的BBC-染色問題,第三章給出了特殊圖類的BBC