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

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

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