如果對一個圖G的每個頂點v,任給一個k-列表L(v),使得G要么沒有正常列表染色,要么至少有兩種正常列表染色,則稱圖G具有M(k)性質(zhì).定義圖G的m數(shù)為使得圖G具有M(k)性質(zhì)的最小整數(shù)k,記為m(G).已有研究表明,當k=3,4時,圖K₍1*r,3*(k-2))具有M(k)性質(zhì),且當r≥2時,m(K₍1*r,3*(k-2)))=k.本文將上述結(jié)論推廣到每一個k,證明了對任意r∈N⁺,k≥3,圖K₍1*r,3*(k-2))具有M(k)性質(zhì),且當k≥4,r≥(k-2)時,m(K₍1*r,3*(k-2)))=k.此外,得到圖K_1,3,3,3的m數(shù)為4,該圖是圖K₍1*r,3*(k-2))中r=1,k=5時的特殊情況,同時也是現(xiàn)有研究中尚未解決的一個問題.

【文章頁數(shù)】：7 頁

【文章目錄】：
1 引言
2 預備知識
3 圖K1*r,3*(k-2)的m數(shù)
4 圖K1,3,3,3的m數(shù)
5 結(jié)論



本文編號：3877540