對(duì)圖G的所有邊進(jìn)行染色,如果染同種顏色的邊構(gòu)成的集合均在G中形成一個(gè)誘導(dǎo)匹配,那么就稱該染色方式為圖G的強(qiáng)邊染色。換言之,如果圖G的任意一個(gè)長(zhǎng)度為3的路徑都具有3種不同的顏色,則這種染色稱為強(qiáng)邊染色。在圖G的所有強(qiáng)邊染色中所需的最少顏色數(shù)稱為圖G的強(qiáng)邊色數(shù),記作χs’(G)。強(qiáng)邊染色問(wèn)題是圖論研究的內(nèi)容之一,在計(jì)算機(jī)科學(xué)及無(wú)線通訊網(wǎng)絡(luò)等領(lǐng)域都有廣泛的應(yīng)用。由于確定圖的強(qiáng)邊色數(shù)是比較困難的,目前大多數(shù)的研究都集中了一些特殊圖類上。本文首先綜述了前人在此方面的研究成果,主要研究了odd圖的結(jié)構(gòu)和性質(zhì),通過(guò)運(yùn)用odd圖研究了平面圖的強(qiáng)邊染色問(wèn)題。本文主要結(jié)果是：如果平面圖G的圍長(zhǎng)至少為10A(G)+26,則它的強(qiáng)邊色數(shù)小于等于2Δ(G)-1。

【文章頁(yè)數(shù)】：25 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
中文摘要
英文摘要
第一章 引言
第二章 基本概念及事實(shí)
    §2.1 證明圖的強(qiáng)邊色數(shù)的一些思想
    §2.2 一些已知的結(jié)果
第三章 ODD圖的結(jié)構(gòu)和性質(zhì)
第四章 定理的證明
參考文獻(xiàn)
致謝



本文編號(hào)：3866280