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

【文章來源】：浙江師范大學浙江省

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

【學位級別】：博士

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



本文編號：3002630