圖的無圈邊色數及相關參數的研究

《圖的無圈邊色數及相關參數的研究》是依託杭州電子科技大學，由舒巧君擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：圖的無圈邊色數及相關參數的研究
• 項目類別：青年科學基金項目
• 項目負責人：舒巧君
• 依託單位：杭州電子科技大學

項目摘要

隨著信息科學與計算機科學的迅猛發展，圖論和組合數學作為其重要理論基礎得到國際數學界和理論計算機界的高度重視和廣泛研究,圖的染色理論更是圖論的重要內容。本項目在現有的工作基礎上,深入研究以下幾個問題：(1) 研究圖的無圈邊染色問題。圍繞著名的無圈邊染色猜想,重點研究4-正則圖和平面圖的無圈邊色數。考慮4-正則圖是否滿足該猜想；確定平面圖的無圈邊色數的更好的上界；研究外可平面圖的無圈邊色數,力爭根據無圈邊色數,刻畫最大度為4的外可平面圖；(2) 研究平面圖的邊-面染色問題。考慮最大度為4和5的平面圖的邊-面染色問題；研究最大度為8的平面圖的邊-面選擇數。本項目的研究內容是國內外研究的熱點課題之一,能豐富相關課題的研究成果,促進一些著名難題的解決或部分解決,有重要的理論意義和套用價值。擬在三年內完成五篇論文,三篇以上被SCI收錄。

結題摘要

圖的染色理論是圖論的重要內容，也是圖論的起源之一，其研究來源於著名的四色問題，具有重要的實際意義和理論意義。如今，它在生產管理、軍事、交通運輸、計算機網路等許多領域都有著重要的套用。圖G的一個正常k-邊染色是指G的邊到集合{1,2,⋯,k}的一個映射，使得任意兩條相鄰的邊染不同的顏色。無圈邊染色最早是由Fiamčіk在1978年提出的。無圈k-邊染色是指圖G的一個正常k-邊染色，使得在此染色下圖G不產生雙色圈。圖G的無圈邊色數定義為a’(G)=min{k│G是無圈k-邊可染的}。Fiamčіk和Alon，Sudakov以及Zaks先後於1978年和2001年分別提出了著名的無圈邊色數猜想，即對任何圖G，a’(G)≤∆(G)+2。諸多學者對此猜想展開了一系列的研究。特別地，找尋一般圖的無圈邊色數的上界、驗證哪些圖類滿足這個猜想等就變得非常有意義。自立項以來，本項目組致力於該課題的研究，我們分別驗證了不含三角形的4-正則圖和含有三角形的4-正則圖都滿足該猜想，結合已有結論，得到4-正則圖是滿足該猜想的。相應的兩個成果均發表在雜誌《Bulletin of the Malaysian Mathematical Sciences Society》上。近期，我們還驗證了不含相交三角形的平面圖和外1-可平面圖是滿足無圈邊染色猜想的。此外，本項目還研究了一些相關的問題，並證得了：(1) g(G)≥6的平面圖是(1,0)-鬆弛強邊(3Δ(G)-1)-可選的。相應的結果發表在雜誌《Discrete Mathematics, Algorithms and Applications》上。這個結論改進了已有的一個結果：g(G)≥7且Δ(G)≥4的平面圖是(1,0)-鬆弛強邊(3Δ(G)-1)-可選的；(2) 若G為只含有一個閉內面的2-連通外平面圖，且該閉內面是一個偶面，那么圖G的(2,1)-點面標號數為6若且唯若G是壞的。相應的成果已被雜誌《浙江師範大學學報(自然科學版)》接收。本項目組總計發表相關論文3篇，其中2篇被SCI檢索。本項目取得的這些研究成果在一定程度上豐富了圖的邊染色相關問題的研究內容。