图的列表强边染色问题

发布时间：2021-04-21 22:36

　　本文介绍最大度为4的图的列表强边染色问题的相关结果。设G是一个图,E（G）与V（G）分别表示它的边集与顶点集。设v∈V（G）,则点v在G中的度数表示为dG（V）,图G的最大度和最小度分别表示为△（G）和δ（G）。图的边染色就是对图中所有的边都染上一个颜色并且要求任意两条相邻的边所染的颜色都不同。图的强边染色则是在边染色的基础上进一步要求任意一条长度为3的路上的三条边所染的颜色也都不同,并且记能够对图G进行强边染色的最小颜色数为图的强边染色数χs’（G）。Erdos和Nesetril在1985年就强边染色问题提出了一个重要猜想:如果图G的最大度为△（G）,那么猜想中△ ≤ 3的情况已经被证明。当△ = 4时,猜想的上界是20,但是目前并没有得到证实,之前最好的结果是在2006年由Cranston证明的,Cranston证明了一个最大度为4的图的强边色数的上界是22,这一结果最近被Huang,Santana和Yu改进为21。关于△>4的情况,目前还没有非常好的研究结果。列表强边染色是广义范围的强边染色,它要求在对图G进行强边染色时,必须预先给G的每条边e都限制一个颜色列表L（e）,而... 

【文章来源】：山东大学山东省 211工程院校 985工程院校 教育部直属院校

【文章页数】：41 页

【学位级别】：硕士

【文章目录】：
中文摘要
英文摘要
符号说明
第一章 前言
    1.1 基本概念
    1.2 强边和列表强边染色问题的背景和发展
    1.3 本文的主要结果及可讨论的相关问题
第二章 预备知识及引用定理
    2.1 距离和距离类概念的引入
    2.2 引用的主要定理和引理
第三章 主定理极小反例的结构逼近
    3.1 极小反例中点和边的性质
    3.2 极小反例中圈的结构
第四章 对于主定理的证明
附录
参考文献
致谢
攻读学位期间发表的学术论文
学位论文评阅及答辩情况表



本文编号：3152616