發(fā)布時間：2020-03-21 14:20

【摘要】：1736年,瑞士數(shù)學(xué)家Euler在他的論文中討論了哥尼斯堡七橋問題,由此誕生了一個全新的數(shù)學(xué)分支-圖論。自從四色猜想被提出之后,圖的染色問題就成為了圖論的一個很重要的研究課題。圖的染色理論在計算機理論、組合最優(yōu)化、信息化科學(xué)和網(wǎng)絡(luò)設(shè)計等方面均有著很重要的應(yīng)用。圖的染色理論有很多分支,如邊染色、點染色、面染色和全染色等。其中研究最多,結(jié)果也較完善的就是圖的邊染色。本文旨在討論圖的一種比較特殊的邊染色-強邊染色。本文主要由五個章節(jié)組成,主要內(nèi)容如下:在第一章,我們首先給出本文用到的基本概念和記號,接著介紹圖的強邊染色的研究背景和研究現(xiàn)狀,最后給出了本文的主要結(jié)果。在第二章,我們著重研究稀疏圖的強邊染色問題。Hocquard等人最早是研究了最大度小于或等于3(Subcubic graphs)的稀疏圖的強邊染色。最近,Bensmail等人研究了最大度為4的稀疏圖的強邊染色,他們證明了最大度為4并且最大平均度分別小于16/5,10/3,17/5,18/5,19/5的圖分別可以用16,17,18,19,20種顏色來強邊染色。我們改進了他們的結(jié)果,證明了最大度為4并且最大平均度分別小于61/18,7/2,18/5,15/4,51/13的圖分別可以用16,17,18,19,20種顏色來強邊染色。在這一章的第二部分,我們證明了最大度為4并且最大平均度分別小于8/3,14/5的圖分別可以用10,11種顏色來強邊染色,并且給出兩個圖說明這兩個最大平均度是接近最優(yōu)的。在第三章,我們證明了最大度為△(△≥6)并且最大平均度小于14/5的圖可以用3△-1種顏色來強邊染色。作為這一結(jié)果的一個結(jié)論,我們得到最大度為△(△ ≥ 6)并且圍長g ≥ 7的平面圖可以用3△-1種顏色來強邊染色,從而改進了Wang的結(jié)果:所有最大度為△ ≥ 6并且圍長g7的平面圖可以用3△種顏色來強邊染色。在第四章,我們首先集中精力研究偽Halin圖的強邊染色問題。偽Halin圖是Halin圖的一般推廣。對Halin圖的強邊染色的研究,最早是Shiu等人,他們證明了Cubic Halin圖強邊色數(shù)至多是9。最近,Hu等人給出了Halin圖的強邊染色數(shù)的一個上界:每個△≥4的Halin圖的強邊染色數(shù)最多是2△+1。這一章我們證明了:每個△ ≥ 4的偽Halin圖的強邊色數(shù)最多是3△-2。需要說明的是,這個上界是接近最好可能的界,因為我們找到一個偽Halin圖,它的強邊色數(shù)剛好等于3△-3。在這一章的最后,我們將主要探討K2,3-minor free圖的強邊色數(shù)問題。我們將證明:每個非空K2,3-minorfree圖的強邊色數(shù)最多是4△-6,并且得到這個界是最好的,因為存在一個非空K2.3-minor free圖的強邊色數(shù)剛好為4△-6。第五章作為本文的結(jié)束部分,我們提出了可以進一步考慮的研究問題。
【學(xué)位授予單位】：華中師范大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【相似文獻】

相關(guān)期刊論文 前10條

1 晏偉峰;曹宇淇;;一道高考染色問題的創(chuàng)新解法及推廣[J];中學(xué)數(shù)學(xué)研究;2019年04期

2 拉毛草;;“無心”和“有心”染色問題[J];數(shù)學(xué)學(xué)習(xí)與研究;2015年11期

3 黃玉嬌;;對一類環(huán)形染色問題的探究[J];中學(xué)數(shù)學(xué)研究;2017年02期

4 郭文欣;;從染色問題談兩個計數(shù)原理的教學(xué)[J];中學(xué)數(shù)學(xué);2008年21期

5 任丹丹;;一道染色問題的妙解[J];上海中學(xué)數(shù)學(xué);2008年01期

6 劉海龍;;染色問題的相互轉(zhuǎn)換探究[J];福建中學(xué)數(shù)學(xué);2009年05期

7 王躍進;牛偉強;;關(guān)于2×n方格的染色問題研究[J];中學(xué)數(shù)學(xué)研究;2011年01期

8 盧建立;任鳳霞;;3×n方格染色問題的兩個新結(jié)果[J];數(shù)學(xué)通報;2011年12期

9 魏躍兵;一類染色問題的解法[J];高中數(shù)學(xué)教與學(xué);2004年07期

10 劉康寧;兩類多面體染色問題的解法[J];中學(xué)數(shù)學(xué);1996年10期

相關(guān)會議論文 前1條

1 王繼勝;;關(guān)于天然染料研究現(xiàn)狀與設(shè)想[A];“五洋杯”2010年江蘇紡織學(xué)術(shù)論文集[C];2011年

相關(guān)重要報紙文章 前10條

1 張裕;淺議彈性織物染色問題[N];中國紡織報;2003年

2 本報記者 劉伊婷;染色米中看不中吃[N];中國質(zhì)量報;2005年

3 陳雍君;染色饅頭不能只追究生產(chǎn)商責(zé)任[N];科技日報;2011年

4 ;紡織是高科技產(chǎn)業(yè)[N];中國工業(yè)報;2009年

5 記者　 張虎;“四新”會議突出染色主題[N];中國紡織報;2006年

6 河北省張家口市宣化區(qū)食品藥品監(jiān)督管理局 閆利霞;做好監(jiān)管工作必須要有“幾把刷子”[N];中國醫(yī)藥報;2013年

7 本版稿件由市老科技工作者協(xié)會提供;壓力變動力創(chuàng)業(yè)做貢獻[N];遼源日報;2005年

8 本報記者 韓競;十年修煉終獲大獎[N];中國紡織報;2005年

9 劉亞力 夏姍姍;中藥材打假須整肅潛規(guī)則[N];中國中醫(yī)藥報;2013年

10 本報記者 俞春華 通訊員 陳守根;承諾重要,守諾更重要[N];中國石化報;2012年

相關(guān)博士學(xué)位論文 前10條

1 胡黎莉;符號圖的整數(shù)流及染色問題研究[D];華中師范大學(xué);2017年

2 周朝陽;圖頂點染色問題中隱含約束關(guān)系研究與應(yīng)用[D];華中科技大學(xué);2017年

3 呂劍波;圖的強邊染色問題研究[D];華中師范大學(xué);2018年

4 李善海;設(shè)計的染色及其相關(guān)問題的研究[D];上海交通大學(xué);2006年

5 侯建鋒;圖上有限制條件的幾類染色問題的研究[D];山東大學(xué);2009年

6 陳敏;運用權(quán)轉(zhuǎn)移方法研究圖的若干染色問題[D];蘇州大學(xué);2011年

7 董愛君;圖的幾類染色問題[D];山東大學(xué);2012年

8 胡小蘭;極值和染色問題的一些新結(jié)果[D];南京大學(xué);2015年

9 梁作松;圖的團橫貫與團染色[D];上海大學(xué);2013年

10 孫林;平面圖和1-平面圖的若干染色問題[D];山東大學(xué);2017年

相關(guān)碩士學(xué)位論文 前10條

1 劉佳;平面圖的（3,0,0）-染色問題[D];山東師范大學(xué);2018年

2 黃麗娜;圖的若干可區(qū)別染色問題的研究[D];蘭州交通大學(xué);2018年

3 張寶晨;圖的列表強邊染色問題[D];山東大學(xué);2018年

4 丁煬柳;不含4,5,7,8-圈的符號圖3染色[D];華中師范大學(xué);2018年

5 藍俊;圖的t-松弛染色問題研究[D];東南大學(xué);2017年

6 王曄;1-平面圖正常點染色問題的研究[D];山東師范大學(xué);2017年

7 梁政;圖染色問題應(yīng)用研究[D];江西師范大學(xué);2016年

8 王瑞琦;圖邊單射染色問題的復(fù)雜性及算法研究[D];南京師范大學(xué);2014年

9 王輝;滿足某些特殊條件的平面圖邊染色問題研究[D];山東大學(xué);2010年

10 朱俊俏;關(guān)于圖的點可區(qū)別染色問題[D];浙江師范大學(xué);2009年

，

本文編號：2593461