【摘要】：令G=(V,E,F)是一個無環(huán)的連通平面圖,其中V表示點集,E表示邊集,F表示面集.圖G的一個正常k-邊面染色是指存在一個映射π:E(G)∪(G)→ {1,2,…,k}滿足:若邊e1與邊e2相鄰,則π(e1)≠ π(e2);若面f1與面f2相鄰,則π(f1)≠ π(f2);若邊e與面f相關(guān)聯(lián),則π(e)≠ π(f).如果G有一個正常k-邊面染色,那么稱G是k-邊面可染的.圖G的邊面色數(shù)xef(G),定義為使得G是邊面k-可染的最小的正整數(shù)k的值.這個概念最早由Jucovic和Fiamcik在1970年前后分別獨立提出.在正常邊面染色定義的基礎(chǔ)上,2016年,Fabrici等人首次提出了弱邊面染色的概念.圖G是弱邊面k-可染的是指存在一個映射π:E(G)∪F(G)→ {1,2,…,k},使得任意兩個相關(guān)聯(lián)的邊和面,任意兩個相鄰的面,以及任意兩條面相鄰的邊都染不同的顏色.這里,我們稱兩條相鄰邊e1和e2是面相鄰的當它們關(guān)聯(lián)同一個面且在該面的邊界上連續(xù)出現(xiàn)時.平面圖G的弱邊面染色數(shù)是指G是弱邊面k-可染的正整數(shù)k的最小值,用xef(G)表示.Fabrici等人證明了每個無環(huán)且無割邊的連通平面圖是弱邊面6-可染的.同時,他們猜想:每個無環(huán)且無割邊的連通平面圖是弱邊面5-可染的.此猜想引起了研究者們的極大興趣.目前為止,該猜想仍未完全解決.因此,研究該染色問題是十分有意義的.本學位論文主要圍繞以上猜想加以研究.學位論文共分為四個章節(jié),如下所示:第一章節(jié),我們首先給出本文中所要用到的圖論的基本概念,然后簡述相關(guān)領(lǐng)域的研究現(xiàn)狀,最后給出本文的主要結(jié)果.第二章節(jié),第三章節(jié)以及第四章節(jié),我們運用數(shù)學歸納方法分別研究了哈林圖、極大平面圖、外平面圖這三類特殊的平面圖.具體來講,我們運用色延拓技巧,組合計數(shù),顏色置換等方法證明了如下三個結(jié)果滿足以上猜想,即:(1)每個哈林圖都是弱邊面5-可染的.(2)每個極大平面圖都是弱邊面5-可染的.(3)每個外平面圖都是弱邊面5-可染的.需要指出,以上三個結(jié)果中的上界5均是最優(yōu)的.
【學位授予單位】：浙江師范大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：O157.5

【相似文獻】

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

1 劉海濤;謝建民;;關(guān)于Kneser圖的一個分數(shù)染色性質(zhì)[J];甘肅高師學報;2016年12期

2 劉海濤;張強;;圖的點可區(qū)別的分數(shù)邊染色數(shù)[J];數(shù)學的實踐與認識;2017年19期

3 達文姣;任志國;;扇、輪和完全圖的r(2)點色數(shù)[J];甘肅聯(lián)合大學學報(自然科學版);2011年02期

4 孔靜;;圖乘積的分數(shù)色數(shù)[J];泰山學院學報;2011年03期

5 黎虹;劉信生;;邊共色數(shù)下圖的分類問題[J];長春工業(yè)大學學報(自然科學版);2011年06期

6 王艷麗;;聯(lián)圖的星色數(shù)[J];黑龍江科技學院學報;2011年06期

7 呂闖;;圖的b-邊染色數(shù)及b-邊連續(xù)性研究[J];吉林化工學院學報;2010年04期

8 亢琳;楊愛民;;θ-圖的對策著色和對策色數(shù)[J];中北大學學報(自然科學版);2009年01期

9 高煒;梁立;夏幼明;;兩種特殊冠圖的相關(guān)分數(shù)色數(shù)研究[J];西安文理學院學報(自然科學版);2009年01期

10 ;升級手機的四大誤區(qū)[J];廣西質(zhì)量監(jiān)督導(dǎo)報;2009年05期

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

1 段華;陳東靈;;系列平行圖的邊面著色[A];中國運籌學會第七屆學術(shù)交流會論文集（上卷）[C];2004年

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

1 家寶 摘;升級手機避免四大誤區(qū)[N];電子報;2006年

2 邢劍;手機唯色[N];中國計算機報;2003年

3 吳暑明;3英寸當?shù)?寬屏幕風靡[N];中國消費者報;2008年

4 黃紹平;LCD產(chǎn)業(yè)和市場新動態(tài)[N];中國電子報;2000年

5 散武 亦言 王立全 吳家豐 路邊 吳家豐 千守 杜滿強;科技展臺[N];中國紡織報;2005年

6 紅梅;松日i-Mat 掌上電腦[N];計算機世界;2003年

7 林宗輝;HDMI 1.3版面世覬覦新一代通用顯示標準寶座[N];電子資訊時報;2006年

8 劉悠;細數(shù)手機六大技術(shù)欺騙[N];中國消費者報;2007年

9 然光;針尖對麥芒[N];中國計算機報;2007年

相關(guān)博士學位論文 前8條

1 王光輝;邊染色圖中的匹配、圈及圖的圓染色[D];山東大學;2007年

2 張霞;圖的f-染色和均勻邊染色[D];山東大學;2007年

3 劉彬;圖的點可區(qū)別染色、列表染色和線性染色[D];山東大學;2010年

4 張瑩麗;圖的一些極值問題研究[D];南京師范大學;2017年

5 李金波;圖上幾類邊覆蓋染色問題的研究[D];山東大學;2011年

6 周文禮;條件染色的算法與復(fù)雜性[D];南開大學;2010年

7 曹倪;圖中的短圈結(jié)構(gòu)及相關(guān)問題研究[D];華東師范大學;2013年

8 史永堂;Randic指標與圖的若干不變量[D];南開大學;2009年

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

1 余夢蕾;平面圖的弱邊面染色[D];浙江師范大學;2018年

2 張家嬌;一些圖的r-動態(tài)染色和列表r-動態(tài)染色問題[D];天津師范大學;2018年

3 王s，

本文編號：2690243