《圖的鄰點可區別邊染色及相關問題研究》是依託浙江師範大學，由黃丹君擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖的鄰點可區別邊染色及相關問題研究
- 項目類別：青年科學基金項目
- 項目負責人：黃丹君
- 依託單位：浙江師範大學
項目摘要,結題摘要,
項目摘要
圖的染色理論在圖論研究中占有重要的地位, 在最最佳化, 計算機理論, 網路設計等方面都有著重要的套用. 本項目在現有工作基礎上, 深入研究以下幾個問題: (一) 研究圖的鄰點可區別邊染色問題. 力爭解決或部分解決平面圖的鄰點可區別邊色數; 刻畫高度平面圖的鄰點可區別邊色數; 並刻畫不含短圈的平面圖的鄰點可區別邊色數; (二) 研究其他一些染色內容: 如圖的鄰點可區別全染色, 無圈邊染色等. 爭取給出圖的鄰點可區別全色數的上界, 探討鄰點可區別邊色數與鄰點可區別全色數之間的關係; 研究平面圖的無圈邊色數並推廣相關的結果. 目前, 有關平面圖的鄰點可區別邊染色問題的研究結果還比較少. 本項目所研究的問題極大地豐富了鄰點可區別染色的研究內容.
結題摘要
圖的染色理論在圖論研究中占有重要的地位; 在最最佳化, 計算機理論, 網路設計等方面都有著重要的套用. 本項目主要研究討論了平面圖的鄰點可區別邊染色、鄰和全染色、距離2-點可區別邊色數等內容. 項目組負責人以及項目組成員嚴格執行既定的研究工作計畫，獲得了以下一些研究內容：1. 證明了最大度至少為12的平面圖的鄰點可區別邊色數至多為Δ+2; 2. 刻畫了最大度至少為16的平面圖的鄰點可區別邊色數; 3. 刻畫了不含3-圈且最大度至少為12的平面圖的鄰點可區別邊色數; 4. 證明了最大度至少為7的二部平面圖的鄰點可區別邊色數至多為Δ+1; 5. 給出了外平面圖的距離2-點可區別邊色數的上界min{2Δ, Δ+8}. 特別的, 當G是二部外平面圖時，其距離2-點可區別邊色數至多為Δ+2; 6. 給出樹的(2,1)-全標號等於Δ+1的一些充分條件; 7. 證明了最大度至少為14的平面圖的鄰和可區別全色數至多為Δ+2. 項目組負責人以及項目組成員總計發表相關論文9篇, 其中SCI檢索論文6篇. 在本項目的基礎上, 項目組成員還獲得兩項相關的國家自然科學基金青年基金項目. 目前, 有關平面圖的鄰點可區別邊染色問題的研究結果還比較少. 本項目所取得的這些結果極大地豐富了鄰點可區別染色的研究內容.
