發(fā)布時(shí)間：2023-10-08 18:34

　　本文中,我們主要研究了邊染色圖中的子圖相關(guān)的問題。給定一個(gè)圖G=(V,E)和G上的一個(gè)邊染色φ:E→{1,2,...,k}。我們稱G的一個(gè)子圖H是正常染色的,如果對(duì)任意H中的兩條相鄰的邊e,e’有φ(e)≠φ(e’)。稱H是彩色的如果對(duì)任意H中的兩條不同的邊e,e’都有φ(e)≠φ(e’)。H是強(qiáng)邊染色的,如果任意H中的長(zhǎng)度不超過3的路都是彩色的。稱G的子圖M是一個(gè)匹配,如果M中的邊是兩兩不相交的。我們首先證明了若強(qiáng)邊染色圖G滿足|G|≥2δ(G)+1,則G中包含大小為δ(G)的彩色匹配。此結(jié)果部分驗(yàn)證了 Wang,Yan和Yu的一個(gè)猜想。其次我們證明了若強(qiáng)邊染色圖G滿足δ(G)>2|G|/3,則G中包含一個(gè)彩色哈密頓圈。這可以被視作是強(qiáng)邊染色圖中的Dirac定理,我們進(jìn)一步提出了一個(gè)相關(guān)的猜測(cè)。關(guān)于一般的邊染色圖,令色度dc(v)為點(diǎn)v的鄰邊使用的顏色的個(gè)數(shù),以及δc(G)為G中點(diǎn)的最小色度。我們研究了其中的正常染色生成樹,并證明了若邊染色圖G滿足δc(G)≥|G|/2,則G中包含一個(gè)正常染色生成樹,并且這里的下界是緊的。Ron Aharoni最近猜想若圖G1,...,Gn是定...

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

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

【文章目錄】：
摘要
ABSTRACT
第一章 緒論
    1.1 基本概念
    1.2 邊染色圖的極值問題
        1.2.1 匹配,圈與樹
        1.2.2 匹配問題的染色版本
        1.2.3 圈問題的染色版本
        1.2.4 邊染色圖中的生成樹
    1.3 吸收技術(shù)
    1.4 主要結(jié)果
第二章 強(qiáng)邊染色圖中的彩色匹配和彩色哈密頓圈
    2.1 強(qiáng)邊染色圖中的彩色匹配
    2.2 強(qiáng)邊染色圖中的彩色哈密頓圈
第三章 邊染色圖中的正常染色生成樹
    3.1 色度條件下的彩色生成樹
    3.2 色度條件下的正常染色生成樹
    3.3 邊染色完全二部圖中的彩色匹配
第四章 圖系統(tǒng)中的彩色哈密頓圈
    4.1 基礎(chǔ)和定義
    4.2 定理4.0.4的證明
    4.3 定理4.0.5的證明
第五章 總結(jié)與展望
    5.1 總結(jié)與展望
參考文獻(xiàn)
致謝
碩士期間發(fā)表的論文
碩士期間獲得的獎(jiǎng)勵(lì)
學(xué)位論文評(píng)閱及答辯情況表



本文編號(hào)：3852566