圖的列表標號著色.pdf

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

2、色,就稱G是k-L<,l>(d<,1>,d<,2>)-choosable.圖的列表標號著色數(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的列表標號著色問題來自所謂的頻道分配模型:不同的電臺要使用無線頻道發(fā)射信號,為了避免相互干擾,位置十分接近的電臺要使用相差足夠遠的頻道,位置較近的

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