圖G的強邊色數(shù),記為χs'(G),是最小的正整數(shù)k,使得圖G存在滿足下述條件的fk-邊著色:每一種顏色的所在的邊集(色類)構(gòu)成該圖的一個導出匹配.本論文僅考慮簡單圖.對一個圖G,我們用△ = △(G)表示圖G的最大度.本碩士論文主要研究平面圖的強邊色數(shù).我們的研究目標是要證明下述猜想:對任一平面圖G,均有χs'(G)≤ △2.針對這一研究目標,我們利用反證法建立了極小反例的若干結(jié)構(gòu)性質(zhì),并由此得到使得該猜想成立的若干圖類.在結(jié)構(gòu)分析過程中,我們采用的一個重要工具是相異代表系(SDR).本文的研究內(nèi)容分為兩部分.第一部分主要討論使得猜想不成立的極小反例平面圖G的結(jié)構(gòu)性質(zhì),其中的極小反例平面圖G滿足:χs'(G)≥ △2 + 1并且|V(G)| + |E(G)丨盡可能小.第二部分主要研究平面二部圖及最大度大于等于8的平面圖的強邊色數(shù)問題.本文的主要結(jié)果如下:(1)若圖G是平面二部圖,則它的強邊色數(shù)χs'(G)≤ △2,其中△7.(2)若圖G是最大度△ ≥ 8的平面圖,則它的強邊色數(shù)χs'(G)≤ △2.(3)極小反例平面圖G不存在1度頂點.(4)若圖G為極小反例平面圖,則對任意的邊xy ∈E(G),均有d(x)+d(y)≥ △ + 2.(5)極小反例平面圖G不存在3-圈,使得3-圈中包含2-頂點,3-頂點和4-頂點.(6)極小反例平面圖G不存在4-圈,使得4-圈中包含2-頂點.(7)極小反例平面圖G是2-連通的.
【學位單位】：鄭州大學
【學位級別】：碩士
【學位年份】：2018
【中圖分類】：O157.5

【相似文獻】

相關期刊論文 前10條

1 李樹霞;阿勇嘎;;圖的擴容圖的色數(shù)、邊色數(shù)[J];內(nèi)蒙古師范大學學報(自然科學漢文版);2018年05期

2 崔俊峰;;圖的點可區(qū)別邊色數(shù)的一個上界[J];首都師范大學學報(自然科學版);2017年01期

3 朱俊俏;卜月華;;星、扇、輪的聯(lián)圖的點可區(qū)別均勻邊色數(shù)[J];浙江師范大學學報(自然科學版);2014年04期

4 王藝橋;舒巧君;;最大度為4的外平面圖的無圈邊色數(shù)[J];浙江師范大學學報(自然科學版);2014年04期

5 馬剛;;一些積圖的點可區(qū)別均勻邊色數(shù)[J];數(shù)學雜志;2014年05期

6 王艷麗;萬慧敏;;笛卡爾積圖的集合邊色數(shù)[J];黑龍江大學自然科學學報;2013年04期

7 馬剛;馬效敏;馬少仙;;圖M(P_n)和M(C_n)的點可區(qū)別均勻邊染色[J];數(shù)學研究;2012年01期

8 劉利群;王治文;陳祥恩;;D(2)-點可區(qū)別正常邊色數(shù)的一個上界[J];數(shù)學的實踐與認識;2012年13期

9 劉信生;路偉華;;圖的點可區(qū)別星邊色數(shù)的一個上界(英文)[J];華東師范大學學報(自然科學版);2012年05期

10 陳祥恩;高毓平;;合成圖的點可區(qū)別正常邊色數(shù)[J];吉林大學學報(理學版);2011年02期

相關會議論文 前3條

1 劉華;趙鵬;馬明;冶建華;張忠輔;;圖S_m*F_n的鄰點可區(qū)別的邊色數(shù)[A];中國運籌學會第七屆學術(shù)交流會論文集（中卷）[C];2004年

2 包世堂;;關于C_m懔C_n的邊色數(shù)[A];中國運籌學會第七屆學術(shù)交流會論文集（上卷）[C];2004年

3 馬剛;;S_m∨F_n的全色數(shù)和點可區(qū)別邊色數(shù)[A];中國運籌學會第九屆學術(shù)交流會論文集[C];2008年

相關博士學位論文 前1條

1 高毓平;圖的邊染色及一些有限制條件的染色[D];山東大學;2016年

相關碩士學位論文 前10條

1 張姍姍;平面圖的強邊色數(shù)研究[D];鄭州大學;2018年

2 元麒旋;圖的剖分的強邊色數(shù)研究[D];鄭州大學;2018年

3 章文超;圖的貪婪博弈邊色數(shù)和游戲邊色數(shù)[D];浙江師范大學;2014年

4 毛新葉;圖的點可區(qū)別邊染色的一些結(jié)果[D];西北師范大學;2009年

5 劉利群;圖的D（2）-點可區(qū)別及點可區(qū)別正常邊染色[D];西北師范大學;2007年

6 郭振香;對具有大圍長可平面圖強邊色數(shù)的研究[D];河南大學;2015年

7 田京京;圖的D（β）-點可區(qū)別邊染色及其概率方法[D];西北師范大學;2007年

8 楊玉紅;若干圖類的星邊染色[D];西北師范大學;2009年

9 鄧凱;圖的星邊染色[D];西北師范大學;2007年

10 朱洪國;圖的強邊染色[D];浙江師范大學;2017年

本文編號：2809217