發(fā)布時(shí)間：2018-02-22 02:44

  本文關(guān)鍵詞： 邊染色 邊覆蓋染色 g-邊覆蓋染色 g-邊覆蓋染色數(shù) g-邊覆蓋臨界圖 幾乎二部圖　出處：《山東師范大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：設(shè)G是一個(gè)簡(jiǎn)單圖,C是一個(gè)顏色集.一個(gè)圖G的正常邊染色是給圖G的邊分配顏色使得每種顏色在G的每個(gè)點(diǎn)處至多出現(xiàn)一次.一個(gè)圖G的邊覆蓋染色是用顏色集C中的顏色給G的邊染色使得每種顏色在每個(gè)點(diǎn)處至少出現(xiàn)1次.一個(gè)圖G的g-邊覆蓋染色是圖的邊覆蓋染色的推廣,它是用顏色集C中的顏色給G的邊染色使得每種顏色在每個(gè)點(diǎn)v∈V(G) 處至少出現(xiàn)g(v)次,這里g是定義在頂點(diǎn)集上的非負(fù)整值函數(shù),即對(duì)任意的點(diǎn)v ∈ V(G),0≤g(v)≤d(v).圖G的g-邊覆蓋染色數(shù)是使得G有g(shù)-邊覆蓋染色的最大的顏色數(shù)目,用Χgc1(G)來表示.宋慧敏和劉桂真在2005年的一個(gè)結(jié)果表明:任意一個(gè)簡(jiǎn)單圖G的g-邊覆蓋染色數(shù)Χgc1(G)=δg(G)或δg(G) - 1,其中δg(G)=(?).如果Χgc1(G)=δg(G),那么稱圖G為g-邊覆蓋染色第一類的,否則稱圖G為g-邊覆蓋染色第二類的.這種確定簡(jiǎn)單圖G是g-邊覆蓋染色第一類的還是第二類的問題稱為圖G的g-邊覆蓋染色的分類問題.本論文主要研究了幾類圖的g-邊覆蓋染色,首先研究了g 邊覆蓋臨界圖的一些性質(zhì),我們找到了g-邊覆蓋臨界圖的一個(gè)新的必要條件,該結(jié)論嚴(yán)格推廣了王紀(jì)輝等人在2007年的一個(gè)結(jié)論以及宋慧敏和劉桂真在2004年的一個(gè)結(jié)論.接著又研究了幾乎二部圖的g-邊覆蓋染色問題,我們得到了一個(gè)幾乎二部圖是g-邊覆蓋第一類圖的一些新的充分條件,我們的某些結(jié)果嚴(yán)格推廣了王紀(jì)輝等人在2006年的一個(gè)結(jié)論以及李金波和劉桂真在2011年的一個(gè)結(jié)論.本文分四章進(jìn)行討論.第一章主要介紹了圖的染色問題的研究背景和意義,給出了文章中涉及的一些基本概念和符號(hào),并闡述了邊覆蓋染色和g-邊覆蓋染色理論的研究現(xiàn)狀,列出了本論文的主要結(jié)果.第二章主要介紹了研究本論文所用到的基本工具,列出了本論文用到的一些重要的引理及其推論.第三章主要討論了幾類圖的g-邊覆蓋染色,對(duì)所得到的結(jié)論進(jìn)行了詳細(xì)的證明,并給出了相關(guān)的推論.第四章給出進(jìn)一步可以研究的問題.
[Abstract]:Let G be a simple graph C is a color set. The normal edge coloring of a graph G is to assign the color to the edge of graph G such that each color appears at most once at each point of G. the edge covering coloring of a graph G is coloring with color. The color in the set C gives the edge coloring of G so that each color appears at each point at least once. The G-edge covering coloring of a graph G is a generalization of the edge covering coloring of a graph. It coloring the edges of G with the colors in the color set C so that each color appears at least at every point v 鈭，

本文編號(hào)：1523455