论文部分内容阅读
本文主要研究图的两类点染色问题:列表染色和DP染色。图G的一个正常点染色是颜色集对G中每个顶点的一个分配,使得任意相邻的两个顶点染不同的颜色。图G的一个列表分配L是指给G的每一个点v分配一个列表为L（v）的色集。给定一个列表分配L,如果G中存在一个正常点染色f,使得对每一个点v∈V（G）都有f（v）∈L（v）,则称G是L-可染的。如果对G每一个列表分配L满足对G的每一个点v有L（v）≥k时,G都是L-可染的,则称G是k-可选的。列表染色是由Vizing,以及Erd（?）s、Rubin和Talor分别独立提出来的。Borodin证明了不含4到9-圈的平面图都是3-可选的,并猜想:每一个不含4到8-圈的平面图都是3-可选的。对于图G的列表染色,因为不同顶点的颜色集可能不一样,所以经常用于正常点染色的一些技巧,比如粘贴点的技巧,并不适用于列表染色。为了克服这个问题,2018年Dvo（?）ák和Postle引入了correspondence coloring（简称“DP染色”）的概念。通过构造图G的辅助图,把G的列表染色问题转化为它对应辅助图中具有一定性质的独立集存在性的问题。Dvo（?）ák和Postle证明了不含4到8-圈的平面图都是3-可选的,解决了Borodin的猜想。Liu和Li证明了不含圈长至多为8的相邻圈的平面图都是3-可选的。Yin和Yu证明了:（1）不含{4,5}-圈且3-圈之间的距离至少是3的平面图都是DP-3-可染的;（2）不含{4,5,6}-圈且3-圈之间的距离至少是2的平面图都是DP-3-可染的。1-平面图的概念是1965年由Ringel首次给出的,并猜想每一个1-平面图都是6-可染的。Borodin证明了猜想中的6成立且是最优的。本文主要研究图的两类点染色问题:列表染色和DP染色。全文共分为五章,主要内容如下:第一章,首先介绍了本文用到的基本概念与符号,接着简述了正常点染色、列表染色和DP染色的相关猜想和研究进展。最后呈现了本文的主要结果。第二章,借助DP染色研究平面图的列表染色问题,得到了以下结果:（1）不含{4,6,8}-圈的平面图都是3-可选的,从而将Wang和Chen（2007）的不含{4,6,8}-圈的平面图都是3-可染改进到3-可选的,同时也改进了Dvo（?）ák和Postle（2018）的结果;（2）不含{4,6,9}-圈的平面图都是3-可选的,从而将Kang、Jin和Wang（2016）的不含{4,6,9}-圈的平面图都是3-可染改进到3-可选的。第三章,研究平面图的DP染色问题,得到了以下结果:（1）{3,4,5}-圈之间的距离至少是3的平面图都是DP-3-可染的,改进了Yin和Yu（2019）的结果;（2）{3,4,5,6}-圈之间的距离至少是2的平面图都是DP-3-可染的,改进了Yin和Yu（2019）的结果;（3）不含{4,5,8,10}-圈的平面图都是DP-3-可染的,从而将Wang和Wu（2011）的不含{4,5,8,10}-圈的平面图都是3-可选的改进到DP-3-可染的。第四章,研究1-平面图的DP染色问题,得到了以下结果:不含{3,4}-圈的1-平面图都是DP-5-可染的。第五章,本文的结束部分,提出了一些进一步研究的问题和潜在的研究方向。