平面图DP-4-可染的一个充分条件

作     者：何晓菲 

作者单位：华中师范大学 

学位级别：硕士

导师姓名：李相文

授予年度：2021年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：平面图 色列表 匹配配置 ML-染色 DP-4-染色 圈 

摘      要：本文主要研究在一定条件下平面图DP染色问题,2017年Postle等人将平面图的列表染色推广到DP染色上,克服了列表染色的局限性.本篇文章是在黄丹君等人已证明的若平面图上每个点不同时与3-,4-,5-和6-圈相关联,则该图是4-可选的基础上,将其结果推广到DP染色上,即得到若平面图G的每个点不同时与3-,4-,5-和6-圈相关联,则图G是DP-4-可染的.主要采用反证法和最小反例的思想.首先假设G的最小反例存在,进而研究了最小反例的一些结构特征,并找到其中存在的一些可约结构,并依据这些可约结构给图G最小反例的每个顶点和面定义初始权值和相应的权转移规则,利用握手引理和欧拉公式求出它点和面的初始权值之和,最后利用权转移的方法分情况讨论证明了的最小反例点和面最终权之和,根据最终权之和和初始权之和不同,证明了图G的最小反例不存在,从而证明了结论的正确性,进一步发展了新的染色理论.