若干圖類的對策染色和鄰強邊染色.pdf

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

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

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

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