本文主要研究圖的無(wú)圈染色與列表染色.G的正常k-點(diǎn)染色是指映射f:V（G）→{1,2,...,k},滿足當(dāng)xy∈E（G）時(shí),/（x）≠f（y）.點(diǎn)色數(shù)χ（G）是指G具有正常k-點(diǎn)染色的最小正整數(shù)k.若G存在一個(gè)正常k-點(diǎn)染色且使得每一個(gè)圈至少用三種顏色,稱其為G的無(wú)圈k-點(diǎn)染色.無(wú)圈點(diǎn)色數(shù)χa（G）是指G具有無(wú)圈k-點(diǎn)染色的最小正整數(shù)k.類似地,我們能定義正常k-邊染色,邊色數(shù)χ’（G）,無(wú)圈k-邊染色,無(wú)圈邊色數(shù)χ’a（G）.指定G的每一個(gè)頂點(diǎn)v一個(gè)顏色表L（v）.稱φ是G的一個(gè)L-點(diǎn)染色,是指對(duì)每一個(gè)v∈V（G）,都存在一個(gè)顏色φ（v）∈L（v）,若xy ∈E（G）,則φ（x）≠φ（y）.若對(duì)任意指定顏色表L,對(duì)每一個(gè)v∈V（G）有|L（v）|≥k,G都存在一個(gè)L-點(diǎn)染色,則稱其為G的列表k-點(diǎn)染色,也稱G是列表k-點(diǎn)可染的或k-點(diǎn)可選的.使得G是k-點(diǎn)可選的最小正整數(shù)k稱為G的列表點(diǎn)色數(shù)或選擇數(shù),簡(jiǎn)記為χl（G）.1-平面圖是指一個(gè)圖可以畫在平面上使得每一條邊最多與一條邊交叉.若1-平面圖G中的任意兩個(gè)交叉點(diǎn)所在的交叉邊的端點(diǎn)是互不相交的,則稱這兩個(gè)交叉點(diǎn)是獨(dú)立的.若1-平面圖中... 

【文章來(lái)源】：浙江師范大學(xué)浙江省

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

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

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 概念與術(shù)語(yǔ)
    1.2 相關(guān)課題的研究概況
        1.2.1 無(wú)圈點(diǎn)染色的研究進(jìn)展
        1.2.2 無(wú)圈邊染色的研究進(jìn)展
        1.2.3 列表點(diǎn)染色的研究進(jìn)展
    1.3 本文主要結(jié)果
第二章 圖的無(wú)圈點(diǎn)染色
    2.1 IC-平面圖的無(wú)圈點(diǎn)染色
        2.1.1 預(yù)備知識(shí)
        2.1.2 關(guān)于上界10的證明
        2.1.3 關(guān)于下界6的討論
    2.2 1-平面圖的無(wú)圈點(diǎn)染色
        2.2.1 無(wú)圈點(diǎn)色數(shù)的一個(gè)新的上界
        2.2.2 三個(gè)關(guān)鍵引理的證明
第三章 圖的無(wú)圈邊染色
    3.1 1-平面圖的無(wú)圈邊染色
        3.1.1 一個(gè)結(jié)構(gòu)定理
        3.1.2無(wú)圈邊色數(shù)的上界?+36
    3.2 不含4-圈的1-平面圖的無(wú)圈邊染色
        3.2.1 結(jié)構(gòu)分析
        3.2.2無(wú)圈邊色數(shù)的上界?+22
    3.3 不含3-圈的1-平面圖的無(wú)圈邊染色
        3.3.1 準(zhǔn)備工作
        3.3.2無(wú)圈邊色數(shù)的上界?+14
第四章 IC-平面圖的列表點(diǎn)染色
    4.1 符號(hào)說(shuō)明
    4.2 IC-平面圖的6-點(diǎn)可選性
    4.3 一個(gè)等價(jià)定理的證明
參考文獻(xiàn)
攻讀學(xué)位期間取得的研究成果
致謝



本文編號(hào)：3002630