圖的列表標(biāo)號(hào)著色.pdf

1、圖G的列表標(biāo)號(hào)著色L<,l>(d<,1>,d<,2>)-labeling,d<,1>,d<,2>∈Z<'+>是一個(gè)從點(diǎn)集V(G)到顏色列表L(V)的函數(shù)f,這里的L(V)={L<,v1>,L<,v2>,…,L<,vn>},L<,vi>是點(diǎn)vi的可用的顏色列表.f是一個(gè)正常著色,如果|f(u)-f(v)|≥d<,i>,1≤i≤2 d(u,v)=i(u,v∈V(G)).如果對(duì)所有滿足|L<,v>|≥k v∈V(G),都可以找到G的一個(gè)正常著

2、色,就稱G是k-L<,l>(d<,1>,d<,2>)-choosable.圖的列表標(biāo)號(hào)著色數(shù)λ<'d<,1>,d<,2>><,l>(G)定義為:λ<'d<,1>,d<,2>><, l>(G)=min{k|Graph G is k-L<,l>(d<,1>,d<,2>)-choosable}.圖G的列表標(biāo)號(hào)著色問(wèn)題來(lái)自所謂的頻道分配模型:不同的電臺(tái)要使用無(wú)線頻道發(fā)射信號(hào),為了避免相互干擾,位置十分接近的電臺(tái)要使用相差足夠遠(yuǎn)的頻道,位置較近的

3、電臺(tái)要使用有一定相差的頻道.將頻道分配給電臺(tái),目標(biāo)是在保證電臺(tái)互不干擾的前提下使用最少的頻道資源.該文中我們主要討論是d<,1>=2,d<,2>=1時(shí)的情況,在第二章中,我們給出了路P<,n>,樹(shù)T,完全圖K<,n>的列表標(biāo)號(hào)著色數(shù),并提出了正常列表的概念.通過(guò)對(duì)路的正常列表的討論給出了圈C<,n>的列表標(biāo)號(hào)著色數(shù).第三章中證明了對(duì)任意圖G,λ<,l>(G)≤△<'2>+2△+1,并給出了平面圖,外平面圖,二部圖,弦圖,強(qiáng)弦圖的λ<,l