《圖的子圖橫貫與子圖迴避染色》是依託上海大學，由單而芳擔任項目負責人的面上項目。
基本介紹
- 中文名：圖的子圖橫貫與子圖迴避染色
- 項目類別：面上項目
- 項目負責人：單而芳
- 依託單位：上海大學
中文摘要,結題摘要,
中文摘要
在圖論中，圖的子圖橫貫概念既是超圖理論中橫貫概念的特例，又可看作圖的團橫貫概念的推廣，而圖的子圖迴避染色問題是與子圖橫貫密切相關的一個問題，可看作圖的團染色問題的推廣。圖的團橫貫問題在上世紀90年初被Erd?s、Gallai和Tuza所研究，它是圖論研究的重要內容，在通訊網路和社會網路拓撲模型的研究中具有廣泛的套用。本項目旨在研究圖的子圖橫貫數和子圖迴避色數界的估計問題和相關的極值問題。主要以圖論和組合最佳化為工具，圍繞組合數學家Erd?s等提出的團橫貫數界的估計問題和最近提出的一些未解決問題開展下列研究工作：搞清楚子圖迴避染色的計算法複雜性；在一般圖上建立子圖橫貫數和子圖迴避色數的界並刻畫相應的極值圖類；在某些重要圖類上建立圖的團橫貫數和團色數的界並刻畫相應的極值圖類；討論這些參數與經典圖參數之間的關係。本項目的研究對深刻揭示圖論的結構性質具有重要意義。
結題摘要
圖的子圖橫貫是圖論研究的重要內容之一，它涉及圖論中的覆蓋、匹配、控制集、獨立集合染色等基本概念，對深刻揭示圖的結構性質具有重要意義,在通訊網路和社會網路等領域均具有廣泛的套用。項目研究的主要內容是圖的團橫貫和團染色問題。確定子圖橫貫數、團橫貫數和團色數的界並刻畫極值圖類，探索這些參數與其他圖參數之間的關係。 Mohar等證明了平面圖是強3-團可染色的. Erdos等曾提出估計平面圖等圖類的團橫貫數的界. 我們建立了外平面圖團橫貫數的緊的上界. 其次，證明了除奇圈外，每個無爪平面圖是2-團可染色的。作為推論獲得了無爪平面圖的團橫貫數的緊的上界，該結果部分回答了Erdos等提出的估計平面圖團橫貫數的界的問題。在上述結果的基礎上，我們推廣Mohar等的結果到K5-minor-free圖上，同時，給出了此類圖的團染色問題的多項式時間算法。 對不含K4無爪4-正則圖，首先給出了其團橫貫數的下界並刻劃了極值圖類；其次，對2-連通的無爪K4-free的4-正則圖，我們證明了其團橫貫數恰好等於[|V(G)|/3]. 對3-正則圖，通過證明每個至多含有兩條割邊的3-正則圖存在一個完美匹配含有每個3-圈的恰好一條邊，證明了此類圖的線圖的橫貫數恰好為|E(G)|/3.同時證明了每個3-正則圖的線圖的橫貫數上、下界。此外，按照圖的圍長，給出了3-正則圖的團橫貫數的可達上界。證明了不含三角形的圖的線圖的團橫貫數不超過其補圖的色數。給出了任意兩個圖的團色數與它們通過笛卡爾積、Kronecker積、強直積或字典積運算後得到的積圖的團色數之間的關係。對圖的符號最大團橫貫函式，建立了的任意圖和團數為k的正則圖的符號最大團橫貫數的可達下界，並刻劃了極值圖類。圖G的Alcuin數是指衝突圖G具有可行運輸方案時船的最小容量.我們確定了最大度不超過5的圖的Alcuin數，並將這一問題推廣到超圖上。 Cerioli等提出了圓弧圖的團染色問題的多項式時間算法。我們進一步給出了圓弧圖的團染色問題的線性時間算法，從而解決了Cerioli等提出的一個未解決問題。對最大度至多為4的圖的團橫貫問題，我們提出了一個多項式時間算法。證明了對圍長為3的3次平面圖上，團橫貫和團獨立集問題是NP-完全的，同時給出了3-正則圖的近似算法。
