《圖的線性蔭度、均勻染色及其相關問題的研究》是依託上海套用技術大學，由陳宏宇擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖的線性蔭度、均勻染色及其相關問題的研究
- 項目類別：青年科學基金項目
- 項目負責人：陳宏宇
- 依託單位：上海套用技術大學
項目摘要,結題摘要,
項目摘要
圖的染色理論在圖論研究中占有重要的地位，在最最佳化、計算機理論、網路設計等方面都有著重要的套用。本項目計畫研究幾個經典的圖的染色問題：線性蔭度、全染色、均勻染色以及它們的推廣：線性k-蔭度，均勻點蔭度等。我們力求確定一些大的圖類，如平面圖、可嵌入到曲面上的圖的線性蔭度，全色數，均勻色數，均勻點蔭度等，解決或部分解決相關的幾個著名猜想。本項目研究的內容主要包括兩個部分：一部分是圖論中經典的染色問題，另一部分是這幾類經典染色問題的推廣，問題的解決對於圖的染色理論將有較大的促進作用。
結題摘要
圖的染色理論在圖論研究中占有重要的地位，在最最佳化、計算機理論、網路設計等方面都有著重要的套用。本項目旨在研究幾類經典的染色問題：線性蔭度、全染色、均勻染色以及它們的推廣：線性k-蔭度，均勻點蔭度等，具體包括：1. 平面圖、可嵌入到曲面上的圖的線性蔭度、線性k- 蔭度； 2. 全染色猜想；3. 平面圖、1-平面圖、可嵌入到曲面上的圖的均勻色數；4. 均勻點蔭度猜想。 對於問題1，利用歐拉公式和權轉移的方法給出了5-圈不與3-圈或4-圈相鄰的平面圖的線性2-蔭度的一個較小的上界，4-圈不共點的平面圖的線性2-蔭度的一個上界，這兩個結果都已經以論文的形式發表。另外對於不含有相交5-圈的平面圖的線性2-蔭度，也給出了它的一個較小的上界，這一結果已經投稿。 對於問題2，通過構造平面圖的一些特殊結構，利用歐拉公式證明了如下圖形的全色數等於Delta+1:（1）最大度Delta至少為7且不含有相鄰5-圈的平面圖，（2）最大度Delta至少為6且不含有相交4-圈和相交5-圈的平面圖，（3）最大度Delta至少為6且不含有6-圈和相鄰5-圈的平面圖，（4）最大度Delta至少為8且不包含含有兩條弦的相鄰i-圈和j-圈，其中i,j屬於{5,6,7}的平面圖，（5）最大度Delta大於等於8的平面圖且對於每一個頂點v都存在兩個整數i,j屬於{3,4,5,6,7}，使得v都不與相鄰的i-圈和j-圈相關聯。另外我們還證明了最大度Delta至少為8且不含有弦5-圈的平面圖的列表邊色數等於Delta，列表全色數等於Delta+1. 這些結果也都已經以論文的形式發表。 對於問題3，因為k-退化圖和k-染色圖之間的關係需要證明，而且研究均勻染色需要用到其中的一些結論，所以此問題還在進一步研究中。 對於問題4，吳建良等人在2013年提出了均勻點蔭度猜想，即：任何簡單圖G的點集合都可以均勻的分成m個子集，並且每一個子集都是一個導出森林，其中Delta（G）表示圖G最大度，m是一個整數，且滿足$m\geq\lceil\frac{Delta+1}{2}\rceil$。我們證明了對於5-退化圖，該猜想成立。該結果也已經以論文的形式發表。 此外我們還研究了1-2-3猜想和平面圖、曲面圖的列表單射染色，相關結果見發表的論文。
