本文關鍵詞：圖的距離為2的點可區(qū)別邊染色

  更多相關文章： 距離為2的點可區(qū)別邊染色 哈林圖 外平面圖 單圈圖

【摘要】：圖G的正常κ邊染色是指存在一個映射φ:E(G)→｛1,2,…,k),使得相鄰的邊e和e,滿足φ(e)≠φ(e')令Cφ(v)表示與點v相關聯的邊的顏色所構成的顏色集合,即Gφ(v)={φ(uv)|uv∈E(G)｝圖G的距離為2的點可區(qū)別邊染色是指,G的一個正常邊染色滿足對任意的兩個距離為2的頂點u和v,都有Cφ(u)≠Cφ(v)圖G的距離為2的點可區(qū)別邊色數Χ'd2(G)是指G有一個距離為2的點可區(qū)別κ-邊染色的最小k值.圖的距離為2的點可區(qū)別邊染色是r-強邊染色的一種特殊情形.圖的r-強邊染色是由Akbari等人和Zhang等人在2006年分別獨立提出的.設r≥1是一個整數,圖G的r-強邊色數Χ's:(G,r)是指G的一個正常邊染色φ滿足對任意兩個頂點u和v,若d(u,v)≤r,都有Cφ(u)≠Cφ(v)的最小顏色數.若r=1,則Χ's:(G,1)=Χ'a(G),Χ'a(G)被稱為鄰點可區(qū)別邊色數.鄰點可區(qū)別邊染色最早是由Zhang,Liu和Wang在2002年提出的,他們猜想：若G是一個|V(G)|≥6的連通圖,則有Χ'a:(G)≤△+2. Balister等人證明了猜想對二部圖和最大度不大于3的圖是成立的Hatami運用概率方法證明了對每一個△1020的圖G,都有Χ'a:(G)≤△+300.Akbari,Bidkhori和Nosrati證明了對每一個圖G,都有Χ'a(G)≤3△.隨后Wang等人將這個界進行了改進,證明了對任意的圖G,Χ'aG)≤2.5△.本學位論文主要研究了圖的距離為2的點可區(qū)別邊染色問題,共分四章.在第一章中,介紹了基本概念和相關領域的研究現狀,并且呈現了本文的主要結果.在第二章中,研究了特殊圖類的距離為2的點可區(qū)別邊染色,確定了一些簡單圖類、單圈圖以及兩類積圖的距離為2的點可區(qū)別邊色數.在第三章中,研究了哈林圖的距離為2的點可區(qū)別邊染色,證明了哈林圖的距離為2的點可區(qū)別邊色數的上界是△+2.在第四章中,研究了外平面圖的距離為2的點可區(qū)別邊染色,先證明了外平面圖的距離為2的點可區(qū)別邊色數的上界是2△,隨后證明將上界改進到了△+8,最后證明了一類特殊外平面圖的距離為2的點可區(qū)別邊色數的上界是△+2.
【關鍵詞】：距離為2的點可區(qū)別邊染色 哈林圖 外平面圖 單圈圖
【學位授予單位】：浙江師范大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要3-4
• Abstract4-8
• 第一章 緒論8-16
• 1.1 基本概念8-9
• 1.2 點可區(qū)別邊染色的研究概況9-14
• 1.3 本文主要結果14-16
• 第二章 特殊圖類的距離為2的點可區(qū)別邊染色16-38
• 2.1 簡單圖類的距離為2的點可區(qū)別邊色數16-19
• 2.2 單圈圖的距離為2的點可區(qū)別邊色數19-24
• 2.3 兩類積圖的距離為2的點可區(qū)別邊色數24-38
• 第三章 哈林圖的距離為2的點可區(qū)別邊染色38-50
• 3.1 預備引理38-45
• 3.2 主要結論及證明45-50
• 第四章 外平面圖的距離為2的點可區(qū)別邊染色50-92
• 4.1 一般上界2Δ50-54
• 4.2 改進的上界Δ+854-71
• 4.2.1 Δ≥5的外平面圖55-65
• 4.2.2 Δ≤4的外平面圖65-71
• 4.3 一類特殊外平面圖的上界Δ+271-92
• 4.3.1 Δ≤3的情形71-76
• 4.3.2 上界Δ+2及其證明76-92
• 參考文獻92-96
• 攻讀學位期間取得的研究成果96-98
• 致謝98-100

【相似文獻】

中國期刊全文數據庫 前10條

1 孔立,倪亞洲;雙外平面圖的邊染色[J];山東教育學院學報;2004年06期

2 孔立;雙外平面圖的邊面染色[J];煙臺師范學院學報(自然科學版);2005年02期

3 劉廣德;;雙外平面圖點染色的一個結果[J];科技信息(學術研究);2008年27期

4 馮紀先;;最大外平面圖和最大平面圖的性質[J];高等數學研究;2013年04期

5 朱秉寰;;可外平面圖的深探特性[J];優(yōu)選與管理科學;1986年03期

6 韓培友,董桂云;關于外平面圖的局部調和著色[J];北京郵電大學學報;1995年01期

7 李敬文，，劉林忠，張忠輔;外平面圖結構性質的若干問題[J];佛山大學學報;1996年06期

8 張?zhí)K梅;外平面圖的邊面列表染色[J];山東農業(yè)大學學報;1998年01期

9 王驍力,張?zhí)K梅,李濤;外平面圖的結構性質及在邊著色上的應用[J];寶雞文理學院學報(自然科學版);1998年03期

10 李濤,王驍力;外平面圖的邊列表染色[J];南都學壇;1998年03期

中國重要會議論文全文數據庫 前2條

1 馮紀先;;最大外平面圖G_(MO)的度[A];第十九屆電工理論學術年會論文集[C];2007年

2 馮紀先;;標定的最大外平面圖G_(MO)的數目[A];第十六屆電工理論學術年會論文集[C];2004年

中國碩士學位論文全文數據庫 前10條

1 劉維;外平面圖的列表著色[D];華中師范大學;2012年

2 王二燕;2-連通外平面圖的r-hued染色和不含鄰接三角形的1-平面圖的無圈邊染色[D];中國礦業(yè)大學;2016年

3 王琰雯;圖的距離為2的點可區(qū)別邊染色[D];浙江師范大學;2016年

4 劉廣德;雙外平面圖的點染色[D];山東大學;2008年

5 孔立;雙外平面圖的染色問題[D];山東大學;2005年

6 單偉;幾類圖的雙約束邊染色問題[D];山東大學;2008年

7 邵澤玲;外平面圖的松弛競賽色數[D];河北工業(yè)大學;2003年

8 方峻峰;平面圖染色問題的研究[D];山東科技大學;2003年

9 張少君;圖的若干特殊正常全染色[D];西北師范大學;2006年

10 許豐偉;圖的完全可定向性[D];浙江師范大學;2010年

本文編號：745052