《邊著色圖的單色和異色子圖及頂點集合劃分問題》是依託南開大學，由李學良擔任項目負責人的面上項目。
基本介紹
- 中文名：邊著色圖的單色和異色子圖及頂點集合劃分問題
- 項目類別：面上項目
- 項目負責人：李學良
- 依託單位：南開大學
- 批准號：10671102
- 申請代碼：A0409
- 負責人職稱：教授
- 研究期限：2007-01-01 至 2009-12-31
- 支持經費：22（萬元）
中文摘要
邊著色圖的單色和異色子圖（圈、路、樹、匹配等）的研究，以及用最少的某種單色或異色子圖去劃分該圖的頂點集合的研究起源於匈牙利學派，國際數學大師Erdos在九十年代前後有多篇文章做這方面的研究，從事過這方面研究的其他重要人物有Alon、Gyarfas、Haxell、Reed、Thomassen、Tuza等，這方面的研究還與Ramsey理論有密切的聯繫，因此我們選擇的研究課題在圖論學科中具有重要的理論意義。從已發表的文章來看，這方面的研究難度比較大，研究進展也比較緩慢。本項目擬解決在色度數及色領域並的條件下最長異色路的最佳下界、異色圈問題。研究最大或完美異色匹配問題。用機率方法研究隨機邊著色下的各種單色和異色子圖的存在機率問題。研究頂點集合的某種單色或異色子圖的最佳劃分問題，研究最佳劃分的算法複雜性、多項式時間算法、近似算法等組合最佳化問題。這些研究將成為圖論學科中新的熱點問題。
