不含给定圈长的平面图的DP-染色

DP-Coloring of Planar Graph without Given Short Cycle

摘要: DP-染色的概念最初被用于证明不含长为4到8短圈的平面图是3-列表可染的, 并且这个结论解决了 部分 Erdo¨s 提出的弱化的列表染色版本的 Steinberg 猜想的部分答案, 之后, DP -染色作为列表 染色的推广, 在染色的研究中受到越来越多的关注. 对于列表染色的研究持续了几十年, 平面图的 3-可选和 4-可选问题都属于 NP -困难问题, 基于此, 近些年我们开始研究在满足己知的某些构型 的平面图是 3- 可选或 4-可选的基础上, 探讨其是否为 DP -3-可染的或 DP -4-可染的. 在这篇文 章里，我们证明了所有不含圈长为 4，5，7，10 的圈的平面图是DP-3-可染的, 拓展了DP-3-可染 的图的范围.

Abstract: The concept of DP-coloring was initially used to prove that a planar graph without cycle of length from 4 to 8 is 3-list-coloring, and this conclusion solves the partial problems of the Steinberg conjecture of the weakened list coloring version proposed by Erdo¨s . As a generalization of list coloring, DP -coloring has received more and more attention in the study of coloring. The research on list coloring has lasted for decades, and the 3-choosable and 4-choosable problems of planar graphs belong to NP -difficult problems. Based on this, in recent years, we have begun to study whether planar graphs satisfying some configurations are DP -3-colorable or DP -4-colorable; moreover, whether they are DP -3-colorable or DP -4-colorable. In this thesis, we prove that all planar graphs without cycles of length 4, 5, 7, 10 are DP-3-colorable, which extends the range of graphs that satisfy DP-3-colorable.