若干圖類的對(duì)策染色和鄰強(qiáng)邊染色.pdf

1、染色問(wèn)題一直是圖論中的熱點(diǎn)話題之一，且至今已有十分豐富的研究結(jié)果.1990年，Bodlaender在關(guān)于計(jì)算機(jī)科學(xué)中的圖論專題討論會(huì)上做了關(guān)于某些色策略的專題報(bào)告[1]，基于圖的正常頂點(diǎn)著色的概念，首先引入了圖的對(duì)策著色的概念.
　　所謂圖的對(duì)策著色，如同兩人（A和B）對(duì)弈，選手A試圖給出圖的正常頂點(diǎn)著色，而選手B則設(shè)法阻止該事件的發(fā)生.設(shè)圖G=(V,E)是n階有限的簡(jiǎn)單圖，t是一個(gè)正的常數(shù)，X是t種顏色的集合，兩個(gè)人在圖G上對(duì)弈

2、，選手A和B交替易手，最后完成對(duì)弈至多移動(dòng)n步，每一步包括一名選手挑選一個(gè)尚未著色的頂點(diǎn)v，且從顏色集X中給它分配一個(gè)顏色a，使得a不同于已分配到v的鄰點(diǎn)的顏色.若n步以后圖G被正常著色，則選手A獲勝:若在該圖的全部頂點(diǎn)被著色之前達(dá)成僵局，即顏色集X中無(wú)色可用，則B獲勝.圖G的對(duì)策色數(shù)是使選手A獲勝的最小的t，記為xg(G).
　　為了簡(jiǎn)單起見(jiàn)，我們分別稱上述對(duì)策著色和對(duì)策色數(shù)為色對(duì)策Ⅰ和對(duì)策色數(shù)Ⅰ.在色對(duì)策Ⅰ的基礎(chǔ)上， Chen

3、，Schelp和Shreve對(duì)選手B再附加條件，提出了一種新的對(duì)策著色，即圖G的對(duì)策著色Ⅱ[2]，這個(gè)條件是限制選手B只能利用選手A已引入的顏色之一，除非他為保證圖著色是正常的而不得不利用X中的一種新顏色.圖G對(duì)策色數(shù)Ⅱ是選手A在對(duì)策著色Ⅱ中有—個(gè)獲勝策略的最小的t，記為x*g(G).關(guān)于圖的對(duì)策著色Ⅱ，目前得到的整體結(jié)果還不是很多.僅知Mycielski圖、路、圈、輪圖及輪扇圖的對(duì)策色數(shù)Ⅱ.本文第二章，利用頂點(diǎn)標(biāo)號(hào)的方法，對(duì)θ圖和廣義

4、θ圖及路的倍圖對(duì)策著色情況進(jìn)行討論，并得出他們的對(duì)策色數(shù)Ⅱ.
　　2002年，張忠輔等人提出圖的鄰點(diǎn)可區(qū)別邊色數(shù)，并得到了圈、完全圖等特殊圖類的鄰強(qiáng)邊色數(shù).本文給出了某些特殊圖類的鄰點(diǎn)可區(qū)別邊色數(shù).在第三章中，運(yùn)用分析結(jié)構(gòu)及歸納方法，得到了若干倍圖的鄰點(diǎn)可區(qū)別邊色數(shù)以及它的界.在第四章中，用分析法得到了積圖的鄰點(diǎn)可區(qū)別邊色數(shù).主要結(jié)果如下:
　　定理x*g(θ)={2,|P1|=1,|P2|=|P3|=3或|P1|=|P2|