關(guān)于無(wú)圈邊著色問(wèn)題的研究.pdf

1、圖的著色問(wèn)題在我們?nèi)粘５纳钪杏兄鴺O其廣泛的應(yīng)用。首先圖著色的理論在組合分析和離散數(shù)學(xué)等數(shù)學(xué)學(xué)科中被廣泛地使用，隨著現(xiàn)代科學(xué)技術(shù)日新月異的發(fā)展，圖著色的相關(guān)理論在交通運(yùn)輸、計(jì)算機(jī)網(wǎng)絡(luò)、工廠的生產(chǎn)管理等生活的多個(gè)方面都有著良好的應(yīng)用效果。此外，圖的著色理論具體的在會(huì)議安排，考試日程的安排以免重復(fù)以及存儲(chǔ)化學(xué)藥劑以免互相反應(yīng)等問(wèn)題上都取得了非常好的效果。
　　 本文是研究簡(jiǎn)單且無(wú)向的有限圖，圖G的頂點(diǎn)集、邊集、面集分別用符號(hào)V(G)

2、、E(G)和F(G)來(lái)表示。
　　 本文共分為四章，主要研究了圖的無(wú)圈邊著色。圖G的正常的邊著色C是指：圖G的相鄰兩條邊得著不同的顏色。圖G的一個(gè)正常邊著色C叫做無(wú)圈邊著色，若這種著色不存在雙色的圈。圖G的無(wú)圈邊色數(shù)是指它的所有無(wú)圈邊著色中所使用顏色數(shù)目的最小值。若一個(gè)圖G能使用k種顏色進(jìn)行無(wú)圈邊著色，就稱(chēng)這種著色是圖G的一個(gè)無(wú)圈k-邊著色。于2001年，Alon等人提出以下的猜想(簡(jiǎn)稱(chēng)AECC)。
　　 猜想1.對(duì)于任