图的无圈染色与列表染色

发布时间：2021-01-27 06:45

　　本文主要研究图的无圈染色与列表染色.G的正常k-点染色是指映射f:V（G）→{1,2,...,k},满足当xy∈E（G）时,/（x）≠f（y）.点色数χ（G）是指G具有正常k-点染色的最小正整数k.若G存在一个正常k-点染色且使得每一个圈至少用三种颜色,称其为G的无圈k-点染色.无圈点色数χa（G）是指G具有无圈k-点染色的最小正整数k.类似地,我们能定义正常k-边染色,边色数χ’（G）,无圈k-边染色,无圈边色数χ’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-点可选的最小正整数k称为G的列表点色数或选择数,简记为χl（G）.1-平面图是指一个图可以画在平面上使得每一条边最多与一条边交叉.若1-平面图G中的任意两个交叉点所在的交叉边的端点是互不相交的,则称这两个交叉点是独立的.若1-平面图中... 

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

【文章页数】：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 无圈点色数的一个新的上界
        2.2.2 三个关键引理的证明
第三章 图的无圈边染色
    3.1 1-平面图的无圈边染色
        3.1.1 一个结构定理
        3.1.2无圈边色数的上界?+36
    3.2 不含4-圈的1-平面图的无圈边染色
        3.2.1 结构分析
        3.2.2无圈边色数的上界?+22
    3.3 不含3-圈的1-平面图的无圈边染色
        3.3.1 准备工作
        3.3.2无圈边色数的上界?+14
第四章 IC-平面图的列表点染色
    4.1 符号说明
    4.2 IC-平面图的6-点可选性
    4.3 一个等价定理的证明
参考文献
攻读学位期间取得的研究成果
致谢



本文编号：3002630