一些特殊圖的線性蔭度和線性2-蔭度問(wèn)題.pdf

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

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

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

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