平面图的DP-着色及图密接性的研究

发布时间：2024-02-16 02:17

　　图的着色问题一直以来是图论的热门经典问题.它最早起源于著名的“四色问题”,已广泛应用于信息论,计算机科学及人工智能等多个领域.本文研究了平面图的DP-着色以及图的密接性质,这主要属于四色问题的延伸范畴.全文共分八章,主要内容如下:在第一章,我们首先给出了文中所需的一些基本概念和符号,接着分别介绍了本文后续各个章节中所涉及的研究问题及背景.在第二章,我们介绍了 Borodin在1996年的一个有关列表着色的猜想:所有不含4到8-圈的平面图是3-可选的.Dvorak和Postle在2017年引入DP-着色的全新概念解决了这一长达20年的猜想,我们在这一结果的基础上做出改进,证明了不含圈长至多为8的相邻圈的平面图是3-可选的.在第三章,基于第二章的研究技巧,我们利用DP-着色试图解决平面图三色领域的相关热门问题.我们研究了平面图的DP-3-着色问题.我们把原先平面图在列表着色中的结果推广到了 DP-着色.我们通过构造一个“近-(k-1)-退化”的子图来解决在这一推广中所遇到的麻烦.在第四章,我们在第三章中给出的结果的基础上,进一步研究了不含{4,a,b,9}-圈的平面图,这里5≤α≠b≤8....

【文章页数】：89 页

【学位级别】：博士

【部分图文】：

图１：在一个不含７－圈的平面图中所有可能的族？??

３－面就称作ｆｃ－簇．下面是一个由??不同的点组成的所有可能的簇在一个不含７－圈的平面图中（在［１８］中，给出了所有??在这样平面图中的２３个族）．??Ａ?？菜図：翁择??（１）?１－ｃｌｕｓｔｅｒ?（２）?２－ｃｌｕｓｔｅｒ?（３）?３－ｃｌｕｓｔｅｒ?（４）?４－ｃｌｕｓｔｅ....

图４：?一个４－圈不是ＤＰ－２－可着色的：左边是一个４－圈Ｇ，右边是图扎．??

?本章我们完成对定理１．３．２的证明．我们主要运用权转移的方法，这个方法基??于强的归纳法．如果一个结构不能出现在一个最小反例Ｇ中，称这个结构是可约??的．我们可以很快的发现定理１．３．１中的所有证明都依赖于下列事实：一个只含??三度点的偶圈是可约的．换句话说，如果Ｃ？是一个所相....

图５：—个１０－圈包含一条３－控制的特殊（３，４，３）－路，一条特殊的（４，４，４，３）－路，和??

？博士学位论文??ＤＯＣＴＯＲＡＬ?ＤＩＳＳＥＲＴＡＴＩＯＮ??图５：—个１０－圈包含一条３－控制的特殊（３，４，３）－路，一条特殊的（４，４，４，３）－路，和??一条极大的（３，４，３）－路，它不是特殊的但用其中的两个点可以组成一条特殊的??（４，３）－路．??引理３．１．３．....

图６：前两个是特殊１０－面（第二张图里／上的４－点也可能在其它位置），中间三个??１０－一１０－．??

博士学位论文??ｙ?ＤＯＣＴＯＲＡＬ．?ＤＩＳＳＥＲＴＡＴＩＯＮ??ｓｐｅｃｉａｌ?ｐｏｏｒ?ｂａｄ??图６：前两个是特殊１０－面（第二张图里／上的４－点也可能在其它位置），中间三个??是穷１０－面，最后一个是坏１０－面．??—如果ｄ（ｔ＞）?２?６，那么ｗ给／誉．??（Ｒ３ｂ）....

本文编号：3900649