《邊染色圖中的異色子圖問題》是依託東南大學，由陳和擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：邊染色圖中的異色子圖問題
- 項目類別：青年科學基金項目
- 項目負責人：陳和
- 依託單位：東南大學
中文摘要,結題摘要,
中文摘要
邊染色圖中的異色子圖（路、圈、匹配、樹等）問題是當代圖論研究的前沿課題之一。這一問題的研究起源於國際數學大師Erdos等人在七十年代對Ramsey理論的推廣，Erdos有多篇文章做這方面的研究，從事過這方面研究的其他著名學者有Alon、Thomassen、Tuza等。本項目旨在將經典圖論的方法和機率方法相結合，力爭給出一般圖中在一些邊染色條件（如色度條件，正常染色條件）下異色長圈和異色長路的長度的最優下界；研究路、圈、樹等常見子圖的anti-Ramsey數或local anti-Ramsey數，確定更多圖類的anti-Ramsey數和local anti-Ramsey數；從算法的角度來考慮異色子圖問題，通過對邊染色圖的結構和異色子圖（包括異色匹配、異色圈、異色生成樹等）存在性的研究，給出其相應的有效算法。這方面的研究已經吸引了許多研究者的關注和興趣，並將引起更大的研究熱潮。
結題摘要
邊染色圖中的特殊著色子圖問題起源於Ramsey 理論，是當代圖論研究的前沿課題之一。本項目對邊染色圖中的單色子圖和異色子圖問題進行了深入系統的研究，在幾個關鍵性問題上取得了實質性進展。（1）研究邊染色圖中的異色長路，分別得到了不含異色三角形的邊染色，正常邊染色，及一般邊染色中異色長路路長的下界，一部分結果已經發表在Utilitas上，另一部分結果已經完成投稿。（2）研究邊染色圖中的異色匹配，對於所有的圖G，得到了關於匹配的Constrained-Ramsey數，相關結果已完成並投稿。（3）研究邊染色圖中的單色高連通子圖，基本確定了2-邊染色完全多部圖中的最大2-連通單色子圖的大小，結果已被套用數學學報（英文版）接收。 （4）研究距離2標號染色及距離2標號染色，得到了關於一些圖類的距離2標號下的實值邊跨度，以及關於一些圖類的邊的距離2標號染色的上下界及關於放鬆的距離2標號染色的一系列結果，這些結果一部分已經發表在東南大學學報（英文版）上，另外有些已完成投稿。以上研究結果推動了相關染色問題的研究，具有重要的理論意義。
