本論文研究了多重列表染色和多重在線列表染色意義下的Ohba猜想和列表染色的推廣.假設(shè)G是一個Hereditary-圖類,即若H∈G,H’是H的導(dǎo)出子圖,則H’∈G.假設(shè)G是一個圖,G相對于G的一個k-染色是指將G的頂點(diǎn)用k種顏色染色,每一個色類導(dǎo)出的子圖屬于G.類似地,可以定義相對于G的列表染色.若G是森林的全體,則對應(yīng)的染色數(shù)稱之為G的點(diǎn)蔭度和列表點(diǎn)蔭度,記為ρ（G）和ρl（G）.Wang,Wu,Yan和Xue研究了 ρ（G）和ρl（G）之間的關(guān)系,以及ρl（G）和χl（G）之間的關(guān)系.他們提出如下猜想:χl（G）≤2ρ（G）.本論文否定了這個猜想.證明了對任意的正整數(shù)k≥2,存在圖 G,ρl（G）=k,χl（G）=k（k+1）.本文定義了圖的在線點(diǎn)蔭度分?jǐn)?shù)選擇數(shù).證明了任意一個有限圖G的在線點(diǎn)蔭度分?jǐn)?shù)選擇數(shù)等于它的分?jǐn)?shù)點(diǎn)蔭度.這一結(jié)果推廣了 Alon,Tuza,Voigt關(guān)于分?jǐn)?shù)選擇數(shù)與分?jǐn)?shù)色數(shù)相等的經(jīng)典結(jié)果.本論文研究了在線版本Ohba猜想的多重列表染色.Ohba猜想斷言若|V（G）|≤2χ（G）+1,則χl（G）=χ（G）.該猜想 2015 年被 Noel,Reed 和 Wu ... 

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

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

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

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 基本概念
        1.1.1 多重在線列表染色
        1.1.2 符號弱列表染色
        1.1.3 圖的廣義列表染色
    1.2 研究現(xiàn)狀
        1.2.1 在線列表染色研究現(xiàn)狀
        1.2.2 符號弱列表染色研究現(xiàn)狀
    1.3 本文主要結(jié)果
第二章 多重在線列表染色
第三章 列表染色的推廣
    3.1 定理1.15的證明
    3.2 定理1.16的證明
    3.3 定理1.17的證明
參考文獻(xiàn)
攻讀學(xué)位期間取得的研究成果
致謝



本文編號：3194071