多重在线列表染色和广义列表染色

发布时间：2021-05-18 15:55

　　本论文研究了多重列表染色和多重在线列表染色意义下的Ohba猜想和列表染色的推广.假设G是一个Hereditary-图类,即若H∈G,H’是H的导出子图,则H’∈G.假设G是一个图,G相对于G的一个k-染色是指将G的顶点用k种颜色染色,每一个色类导出的子图属于G.类似地,可以定义相对于G的列表染色.若G是森林的全体,则对应的染色数称之为G的点荫度和列表点荫度,记为ρ（G）和ρl（G）.Wang,Wu,Yan和Xue研究了 ρ（G）和ρl（G）之间的关系,以及ρl（G）和χl（G）之间的关系.他们提出如下猜想:χl（G）≤2ρ（G）.本论文否定了这个猜想.证明了对任意的正整数k≥2,存在图 G,ρl（G）=k,χl（G）=k（k+1）.本文定义了图的在线点荫度分数选择数.证明了任意一个有限图G的在线点荫度分数选择数等于它的分数点荫度.这一结果推广了 Alon,Tuza,Voigt关于分数选择数与分数色数相等的经典结果.本论文研究了在线版本Ohba猜想的多重列表染色.Ohba猜想断言若|V（G）|≤2χ（G）+1,则χl（G）=χ（G）.该猜想 2015 年被 Noel,Reed 和 Wu ... 

【文章来源】：浙江师范大学浙江省

【文章页数】：35 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 基本概念
        1.1.1 多重在线列表染色
        1.1.2 符号弱列表染色
        1.1.3 图的广义列表染色
    1.2 研究现状
        1.2.1 在线列表染色研究现状
        1.2.2 符号弱列表染色研究现状
    1.3 本文主要结果
第二章 多重在线列表染色
第三章 列表染色的推广
    3.1 定理1.15的证明
    3.2 定理1.16的证明
    3.3 定理1.17的证明
参考文献
攻读学位期间取得的研究成果
致谢



本文编号：3194071