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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

相關(guān)會(huì)議論文 前3條

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10 朱洪國;圖的強(qiáng)邊染色[D];浙江師范大學(xué);2017年

本文編號(hào)：2809217