帶有鄰域限制的三類(lèi)染色問(wèn)題.pdf

1、由于圖論理論在現(xiàn)代應(yīng)用數(shù)學(xué)中的重要作用以及計(jì)算機(jī)科學(xué)和組合優(yōu)化的發(fā)展，圖論作為數(shù)學(xué)科學(xué)中一門(mén)獨(dú)立的學(xué)科飛速發(fā)展起來(lái)．圖的染色問(wèn)題是圖論研究中一個(gè)非常活躍的領(lǐng)域，有著很好的理論探討價(jià)值和實(shí)際意義．基于此，數(shù)學(xué)家們?cè)趥鹘y(tǒng)的點(diǎn)染色，邊染色的基礎(chǔ)上添加各種限制，拓展出了許多新的染色分支．
　　賴宏建等人于2006年在《離散數(shù)學(xué)》上提出了條件染色的概念并得到了一些結(jié)論，在《圖的條件染色》一文中，他們提出并討論了一些特殊圖類(lèi)的條件色數(shù)，一般圖

2、的條件色數(shù)上界以及正常圖的幾個(gè)充分條件等．2002年，G．Hahn，J．Kratochvil，J．Siran，D．Sottean等人在《離散數(shù)學(xué)》上發(fā)表文章《圖的單射色數(shù)》，在文中他們首次提出了單射染色．自此，在這個(gè)問(wèn)題，特別是滿足一定條件的平面圖的單射色數(shù)方面，涌現(xiàn)出很多好的結(jié)果．2008年，孫磊，劉曉曉提出了鄰域限制標(biāo)號(hào)的概念，在劉曉曉的碩士畢業(yè)論文中，她研究了滿足一定條件的圖的鄰域限制標(biāo)號(hào)數(shù)下界，圈和樹(shù)的鄰域限制標(biāo)號(hào)數(shù)以及鄰域限制

3、標(biāo)號(hào)的幾個(gè)性質(zhì)等．這三類(lèi)染色問(wèn)題都是帶有鄰域限制的染色問(wèn)題．
　　在本文第一章里，主要介紹了文章中涉及的一此基本概念與符號(hào)，描述了圖的染色問(wèn)題的發(fā)展及現(xiàn)狀.
　　在第二章中，主要研究了圖的條件染色問(wèn)題，給出了正常圖及r-正常圖的幾個(gè)充分條件并改講了圖的條件色數(shù)的上界.
　　在第三章中，主要研究了圖的單射染色問(wèn)題，介紹了在研究平面圖中用到的一此特殊的概念，符號(hào)以及部分已有的研究成果.同時(shí)，給出了圍長(zhǎng)不小于6時(shí)圖的單射色數(shù)