幾類特殊平面圖上的二人對(duì)策著色.pdf

1、這篇文章討論在圖上的二人對(duì)策著色:設(shè)t,d是正整數(shù),X是t種顏色的集合.由Alice開(kāi)始,Alice和Bob兩個(gè)人輪流選取X中的顏色對(duì)圖G的頂點(diǎn)進(jìn)行著色,每次每人著一個(gè)頂點(diǎn).如果圖G的頂點(diǎn)x著顏色c后,由圖G著顏色c的頂點(diǎn)導(dǎo)出的子圖的頂點(diǎn)最大度至多是d,則稱顏色c對(duì)頂點(diǎn)x來(lái)說(shuō)是可行色.每次Alice和Bob必須用可行色對(duì)圖G的未被著色的頂點(diǎn)進(jìn)行著色.如果圖G的所有頂點(diǎn)都被著色或者還有頂點(diǎn)沒(méi)有可行色去著色,則著色結(jié)束.Alice的目標(biāo)是實(shí)

2、現(xiàn)對(duì)圖G的所有頂點(diǎn)進(jìn)行可行著色,而B(niǎo)ob的目標(biāo)就是要破壞Alice實(shí)現(xiàn)她的目標(biāo).這篇文章主要運(yùn)用分裂已著色頂點(diǎn)的方法證明了如果圖G是二叉樹(shù),且d≥2,則X<,g><'(d)>(G)≤2.如果圖G是樹(shù)且d≥3,則X<,g><'(d)>(G)≤2.設(shè)G是外部平面圖且d≥2,G′是G的2-連通的三角剖分.若T<,G′>是一條路,則X<,g><'(d)>(G)≤5.設(shè)G是外部平面圖且d≥3,G′是G的2-連通的三角剖分,D是T<,G′>的最小控