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

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

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