Halin圖的若干染色問題研究.pdf

1、圖染色理論是圖論的重要內(nèi)容，也是圖論的起源之一.幾百年來，它深深地吸引著數(shù)學家們的眼球.現(xiàn)如今，它在生產(chǎn)管理、軍事、交通運輸、計算機網(wǎng)絡等許多領域都有著重要的應用.Halin圖是一類特殊的平面圖，它是R.Halin于1969年作為極小3-連通圖而提出的.由于其自身的特殊結(jié)構(gòu)，近年來，Halin圖的染色問題已成為圖染色理論的熱點問題. 本文主要研究Halin圖的三種染色：點強全染色(VSTC)、鄰強邊染色(ASEC)以及強染色.

2、 針對Halin圖的點強全染色問題，本文首先提出了輪圖Wp的點強全染色算法.并針對一般的Halin圖，構(gòu)造性地提出了解決Halin圖的點強全染色問題的有效染色法——逐圈染色法.利用逐圈染色法可在多項式時間內(nèi)完成Halin圖的點強全染色.同時還確定了△(G)=3的Halin圖的點強全色數(shù)的上下界.上界是6，下界是5.確定了項鏈Neh的強色數(shù)和點強全色數(shù)，并提出了各自的染色方案.在△(G)=3的Halin圖的點邊全染色方案的基礎上，提