《圖的幾類(g,f)-染色及其算法研究》是依託山東師範大學，由張霞擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖的幾類(g,f)-染色及其算法研究
- 項目類別：青年科學基金項目
- 項目負責人：張霞
- 依託單位：山東師範大學
項目摘要,結題摘要,
項目摘要
本項目主要研究圖的f-染色、g-邊覆蓋染色、均勻邊染色等幾類(g,f)-染色問題.它們是一般圖的邊染色和邊覆蓋染色的推廣,在排序問題,計算機檔案傳輸和網路設計中有重要的套用.該問題是計算機科學家首先提出的,有許多新問題和猜想沒有解決.申請者和項目組成員已做過相關的研究並獲得若干成果.申請者首先提出關於f-染色的分類問題、f-臨界圖等概念並對其研究，並首次套用f-染色的方法解決了圖的均勻邊染色中的一個猜想．本項目主要研究(g,f)-染色中的分類問題，圖的f-染色和g-邊覆蓋染色的色數、色數的界,有關這兩種邊染色的臨界圖的性質、兩種邊染色的分數染色以及有關的算法.力求解決關於f-染色和臨界圖的兩個猜想.同時,我們還研究同上述邊染色關係密切的均勻邊染色．把染色和因子分解兩種方法結合起來進行研究，將得到一些新的理論和算法.
結題摘要
本項目主要研究圖的f-染色、g-邊覆蓋染色、均勻邊染色等幾類(g,f)-染色問題.它們是圖的邊染色和邊覆蓋染色的推廣,在時間表問題,計算機檔案傳輸和網路設計中有重要的套用. 在本項目的資助下，項目組在上述問題上取得了一系列的重要成果，解決了兩個相關的猜想,在國際權威學術期刊《J. Graph Theory》、《Ars Combinatoria》等發表了14篇SCI和2篇EI論文. 特別的，主持人張霞與劉桂真教授合作解決了A.J.W. Hilton 提出的關於圖的均勻邊染色問題的一個猜想，並且給出一個比其更強的結果，將圖存在k色均勻邊染色的充分條件由之前的“無k-核或k-核為孤立點集”直接推廣到允許k-核出現圈的“k-可剝離”，此項工作具有突破性意義.
