一些特殊圖的線性蔭度和線性2-蔭度問題.pdf

1、圖的染色問題起源于地圖的染色問題，即著名的四色猜想：每幅地圖都可以用四種顏色著色，并且相鄰的國家所染顏色不同.數(shù)學(xué)家赫伍德首先證明了五色定理，得出每張地圖都能用五種或者更少的顏色染色.隨后，關(guān)于四色猜想的證明出現(xiàn)了很多版本，但是過程都很繁瑣.直到1976年6月，美國數(shù)學(xué)家Appel和Haken經(jīng)過四年的艱苦工作，終于用計算機完成了對四色猜想的證明，四色猜想改稱為四色定理.但是，很多數(shù)學(xué)家并沒有滿足于計算機取得的現(xiàn)有成就，他們更希望得到一

2、種簡單到可以通過書面表達的證明方法.這個想法目前尚未實現(xiàn).
　　圖的染色問題作為圖論研宄的一個重要分支，在實際生活中有著廣泛的應(yīng)用.而圖的線性蔭度和線性fc-蔭度問題作為圖的邊染色問題的一種，在圖的分解方面有著重要的研宄意義.給定一個圖G,若G可以被劃分為m個邊互不相交的線性森林，則稱最小整數(shù)m為圖G的線性蔭度，記為la(G);若G可以被劃分m個邊互不相交的線性fc-森林，則稱最小整數(shù)m為圖G的線性fc-蔭度，記為^(G).

3、>　　近年來，圖的蔭度問題得到了廣泛的研宄，但是關(guān)于圖的線性fc-蔭度的研宄卻相對較少.本論文在已有研宄結(jié)果的基礎(chǔ)上，對圖的線性蔭度和線fc-蔭度(fc=2時)兩種問題進行新的研宄.論文的主要內(nèi)容分為以下四個部分：
　　第一章,介紹了論文涉及的一些基本概念和符號的定義以及圖的線性蔭度和線性fc-蔭度問題的產(chǎn)生和發(fā)展，并且給出了本論文得到的主要結(jié)果.
　　第二章，研宄不含連續(xù)三個3-面的可平面圖的線性蔭度問題.首先，利用圖的線

4、性染色理論對fc-刪除-極小圖的結(jié)構(gòu)性質(zhì)進行了研宄，然后運用權(quán)轉(zhuǎn)移方法證明了不含連續(xù)三個3-面的可平面圖的線性蔭度滿足la(G)<4,當(dāng)A(G)<8時.
　　第三章，研宄具有性質(zhì)Pk的圖類的線性2-蔭度問題.通過對所研宄的圖類進行邊劃分得到相關(guān)的結(jié)構(gòu)引理，進而在已有結(jié)論的基礎(chǔ)上完成了對本章主要結(jié)論的證明.最后，運用所得結(jié)果改進了一些可平面圖的線性2-蔭度的上界.
　　第四章，總結(jié)部分.對論文中有進一步研宄空間和意義的問題做了