《圖的染色方法及其套用》是依託山東大學，由劉桂真擔任項目負責人的面上項目。
基本介紹
- 中文名：圖的染色方法及其套用
- 項目類別：面上項目
- 項目負責人：劉桂真
- 依託單位：山東大學
中文摘要,結題摘要,
中文摘要
圖的染色方法在計算機科學中有重要的套用。如排序問題,計算機檔案傳輸問題，網路設計，Jacobian矩陣，Hessian矩陣的計算以及生物信息計算等問題都用到圖的染色方法。本項目主要研究圖論中有約束條件的染色問題以及有關的算法。圖的(g,f)-染色是一般圖的邊染色問題的推廣。當g=0,f=1 時(g,f)-染色即為圖的一般邊染色。該問題是計算機科學家首先提出的,有許多新問題和猜想沒有解決。特別我們研究f-染色和g-邊覆蓋染色以及與這些染色有關的均勻染色，全染色，列表染色, [r,s,t]-染色和圓染色。提出了新的研究問題。研究這幾類染色的臨界圖的性質。力求解決幾個染色問題的猜想。確定某些特殊圖的這幾類染色的色數。特別是關於1-平面圖的色數。我們將染色和因子分解兩種方法結合起來進行研究.將得到一些新的理論和方法.本項目所研究的問題有些是圖的染色理論中著名的問題，有些是開創性的工作
結題摘要
圖的染色方法在計算機科學中有重要的套用。在Jacobian矩陣和Hessian矩陣的計算等問題中都用到圖的染色方法。本項目主要研究圖論中有約束條件的染色問題以及有關的算法。圖的(g,f)-染色是一般圖的邊染色問題的推廣。當g=0,f=1 時(g,f)-染色即為圖的一般邊染色。該問題是計算機科學家首先提出的,有許多新問題和猜想沒有解決。 我們研究f-染色和g-邊覆蓋染色以及與這些染色有關的均勻染色，全染色，列表染色, [r,s,t]-染色和圓染色。提出了新的研究問題。研究這幾類染色的臨界圖的性質。證明了幾個染色問題的猜想對某些圖成立。確定了某些特殊圖的這幾類染色的色數，特別是關於1-平面圖的色數。我們將染色和因子分解兩種方法結合起來進行研究.得到了一些新的理論和方法.本項目所研究的問題有關於計算機科學和圖論。這些問題的解決將促進圖的染色理論的發展。
