《邊染色圖的單色子圖和雜色子圖劃分問題》是依託浙江師範大學，由金澤民擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：邊染色圖的單色子圖和雜色子圖劃分問題
- 項目類別：青年科學基金項目
- 項目負責人：金澤民
- 依託單位：浙江師範大學
- 支持經費：15（萬元）
- 研究期限：2008-01-01 至 2010-12-31
- 負責人職稱：副教授
- 申請代碼：A0409
- 批准號：10701065
項目摘要
邊染色圖的單色子圖或雜色子圖劃分問題，就是用頂點不相交的某種單色子圖或雜色子圖去劃分給定圖的頂點集合。Erdos、Gyarfas等於上世紀八、九十年代對此開展了一系列的研究。該問題與Ramsey理論有著十分密切的聯繫，在圖論學科的研究中具有重要的理論意義，這方面問題及其相關的單色（雜色）子圖問題引起了多位國際著名學者的研究興趣，包括Alon，Reed，Thomassen，Tuza等。迄今該問題的研究進展仍比較緩慢，具有較大的難度。本項目擬研究一般圖類中某種單色子圖和雜色子圖的劃分問題；從算法的角度研究邊染色圖的單色子圖和雜色子圖劃分所相關的組合最佳化問題，確定其算法複雜性，對某些問題設計出有效算法或近似算法；研究邊染色圖中單色子圖和雜色子圖劃分問題的各種推廣情形。這方面的研究吸引著越來越多研究者的關注和興趣，將成為圖論學科中的熱點問題之一。
