没有3,8,9-圈的可平面图是DP-3-可着色的
发布时间：2021-11-15 12:51
如果一个图G的点集可以被划分为k个独立集,那么该图G是k-可正常着色的,即使得图G中的相邻两点着不同的颜色。如果给图G=（V,E）的每一个顶点v一个颜色列表L（v）,对于图G的每一个顶点v,G都存在一个正常着色c使得c（v）∈L（v）,称图G=（V,E）是L-可着色的。如果图G的每一个顶点v的颜色列表集|L（v）|≥k,对于图G的每一个顶点v,图G都存在一个正常着色c使得c（v）∈L（v）,那么图G是k-可选的。本文主要研究平面图的DP-着色。作为列表染色的推广,也就是DP-着色,是由Devorak和Postle在2018年提出来的。对于列表染色来说,把着相同颜色的相邻点对之间进行匹配,但对于DP-着色来说,相邻点对之间的匹配是可以任意给的。平面图中有一部分关于列表着色的结论可以推广到DP-着色,但是大部分的列表着色的结论是不可以推广到DP-着色的。正如Bernshteyn和Kostochka指出:DP-着色和列表着色是不同的。因此将许多学者和兴趣爱好者的目光从列表染色转移到DP-着色上是一个很自然的事情。由于已经证明了每个可平面图是DP-5-可着色的,那么能不能把色数的界给降一点呢?...
【文章来源】：华中师范大学湖北省 211工程院校 教育部直属院校
【文章页数】：42 页
【学位级别】：硕士
【部分图文】：
图１：?一些图结构??
领士学位论文??ＭＡＳＴＥＲ＇Ｓ?ＴＨＥＳＩＳ??ｋＶ??＼?／?＞—／?＼—ｆｆ?＼—ｙ??／—ｖ?／—＼?／—）—ｖ??７＾＾??（１）?（２）?（３）?（４）??图５：坏的４〇－面的相关结构阁??｜?＋?２ｘ＊?＋?２ｘｉ?＋?２ｘｉ＞０。如果相邻的都是５＋－点时，比较坏的情况是以下两种情??况：图⑶中的４－点都变成５＋－点，那么此时有２ｘｉ＞４ｘ＾故０，图⑷中??的４－点都是５＋－点，那么此时有／／（ｒ）２／ｘ（ｒ）?＋?２ｘ｜＋２ｘ！?＋?２ｘｉ２〇。如果图（３）中??的?４？点有一个是?５＋－点，／／（７１）?２＂（Ｔ）?＋?２ｘ｜＋２ｘ！?＋?２ｘｉ?＋?ｌｘ｜?之?０，如果图（４）??中的４－点有一个是５＋－点，那么此时有／／（ｒ）?２／Ｉ（ｒ）＋２ｘ｜?＋?２ｘｉ?＋?２ｘ忐＋?２ｘ｜?２〇，??或者是图（５）的情况，／／（ｒ）?＞?＂（ｒ）?＋?２ｘｆ?＋?２ｘ?長＋?ｌｘ?忐＋?２ｘ｜＋ｌｘ?士?２?０。??情形４?４ｃｒ面上相邻３个４＋－点时，则至少相邻１个１０＋－面，由／？⑴和／？⑷，??＞?ｆｉ｛Ｔ）?＋?ｌｘ＾?＋?ｌｘｉ?＋?ｌｘｉ＞０〇??情形５?知－面上相邻４个４＋－点时，由权转移规则，有／ｉ＇（ｒ）２〇。?□??引理４．３．如果：Ｔ是坏的４〇－面和它上面的１０个顶点导出的子图，那么坏的??知－面和其上所有顶点导出的子图的最小最终权值在５－面上各有一个４－点且该４－点??不与４〇－面上的点相邻时取得，且／／（ｒ）?２?０。??证明：由引理３．２的（１）、（７）和（８），坏的４０－面至少存在２个４＋－点且不在??同一个５－面上。当坏的４〇－面上的４＋－点都是４－点的
硕士学位论文??ＭＡＳＴＥＲ’Ｓ?ＴＨＥＳＩＳ??ｉ?－ｔ?；—？’?ｘｉ—?？?＾?？?？?ｔ??ｔ＝ｎ?口：?］?：：?：?ｒａ?ｒａ：??ｙ?９?Ｗ＇＼?ｑ??？?？?？?—ｒｖ?—？?？?？??—ｆｈ￣￣？￣￣－ｔ?ｔ￣￣ｔ——？?－ｆ￣￣ｆ?？，?￣ｉ?ｆ?ｆ￣?ｆ＾??Ｘｍ?．１－４—３．?ｉ—ｍ??？???ｆ——ｔ——ｆ??ｒ：】??图６：?ｌ?－?５－面的相关结构图??３－点，只会增加不会减少；所以有当坏的４Ｃ－面上出现２个４－点、出现２个５＋－点??或者出现１个４－点和１个５＋－点的是情况是糟糕的。下面我们就这三种情况进行讨??论：??情形１当坏的４〇－面上出现２个４－点的时候，５－面上各有一个４－点且该４－点不与??４〇－面上的点相邻时是最坏的，此时ｆ（ｒ）?２?／ｉ（ｒ）?＋?Ｓｘ｜＋４ｘｆ?＋?４ｘ吉２（）。??情形２当坏的４〇－面上出现２个５＋－点的时候，５－面上各有一个５＋－点且该５＋－点不??与４。－面上的点相邻时是最坏的，此时／Ａ：Ｔ）仝ｍＣＯ?＋?８ｘ｜?＋?４ｘｆ?＋?２ｘｉ＞０。??情形３当坏的４Ｑ－面上出现１个４－点和１个５＋－点的时候，５－面上各有一个??４－点和５＋－点且该４－点和５＋－点不与４０－面上的点相邻时是最坏的，此时／／（乃２??＂（Ｔ）?＋?８ｘ｜?＋?４ｘ．?＋?ｌｘ｜?＋?２ｘ咅仝０。而且我们还可以得到，这三种情形下，??情形〗是最终权值最小的一个，且不低于〇。?口??弓丨理４．４．如果：Ｔ是Ｉ?—?５－面和它上面的８个顶点导出的子图，則Ｗ）?２?〇。??证明：由引理３．４的（１）、（２）、（３）和（４），?４！?—?５－面至
本文编号：3496816
【文章来源】：华中师范大学湖北省 211工程院校 教育部直属院校
【文章页数】：42 页
【学位级别】：硕士
【部分图文】：
图１：?一些图结构??
领士学位论文??ＭＡＳＴＥＲ＇Ｓ?ＴＨＥＳＩＳ??ｋＶ??＼?／?＞—／?＼—ｆｆ?＼—ｙ??／—ｖ?／—＼?／—）—ｖ??７＾＾??（１）?（２）?（３）?（４）??图５：坏的４〇－面的相关结构阁??｜?＋?２ｘ＊?＋?２ｘｉ?＋?２ｘｉ＞０。如果相邻的都是５＋－点时，比较坏的情况是以下两种情??况：图⑶中的４－点都变成５＋－点，那么此时有２ｘｉ＞４ｘ＾故０，图⑷中??的４－点都是５＋－点，那么此时有／／（ｒ）２／ｘ（ｒ）?＋?２ｘ｜＋２ｘ！?＋?２ｘｉ２〇。如果图（３）中??的?４？点有一个是?５＋－点，／／（７１）?２＂（Ｔ）?＋?２ｘ｜＋２ｘ！?＋?２ｘｉ?＋?ｌｘ｜?之?０，如果图（４）??中的４－点有一个是５＋－点，那么此时有／／（ｒ）?２／Ｉ（ｒ）＋２ｘ｜?＋?２ｘｉ?＋?２ｘ忐＋?２ｘ｜?２〇，??或者是图（５）的情况，／／（ｒ）?＞?＂（ｒ）?＋?２ｘｆ?＋?２ｘ?長＋?ｌｘ?忐＋?２ｘ｜＋ｌｘ?士?２?０。??情形４?４ｃｒ面上相邻３个４＋－点时，则至少相邻１个１０＋－面，由／？⑴和／？⑷，??＞?ｆｉ｛Ｔ）?＋?ｌｘ＾?＋?ｌｘｉ?＋?ｌｘｉ＞０〇??情形５?知－面上相邻４个４＋－点时，由权转移规则，有／ｉ＇（ｒ）２〇。?□??引理４．３．如果：Ｔ是坏的４〇－面和它上面的１０个顶点导出的子图，那么坏的??知－面和其上所有顶点导出的子图的最小最终权值在５－面上各有一个４－点且该４－点??不与４〇－面上的点相邻时取得，且／／（ｒ）?２?０。??证明：由引理３．２的（１）、（７）和（８），坏的４０－面至少存在２个４＋－点且不在??同一个５－面上。当坏的４〇－面上的４＋－点都是４－点的
硕士学位论文??ＭＡＳＴＥＲ’Ｓ?ＴＨＥＳＩＳ??ｉ?－ｔ?；—？’?ｘｉ—?？?＾?？?？?ｔ??ｔ＝ｎ?口：?］?：：?：?ｒａ?ｒａ：??ｙ?９?Ｗ＇＼?ｑ??？?？?？?—ｒｖ?—？?？?？??—ｆｈ￣￣？￣￣－ｔ?ｔ￣￣ｔ——？?－ｆ￣￣ｆ?？，?￣ｉ?ｆ?ｆ￣?ｆ＾??Ｘｍ?．１－４—３．?ｉ—ｍ??？???ｆ——ｔ——ｆ??ｒ：】??图６：?ｌ?－?５－面的相关结构图??３－点，只会增加不会减少；所以有当坏的４Ｃ－面上出现２个４－点、出现２个５＋－点??或者出现１个４－点和１个５＋－点的是情况是糟糕的。下面我们就这三种情况进行讨??论：??情形１当坏的４〇－面上出现２个４－点的时候，５－面上各有一个４－点且该４－点不与??４〇－面上的点相邻时是最坏的，此时ｆ（ｒ）?２?／ｉ（ｒ）?＋?Ｓｘ｜＋４ｘｆ?＋?４ｘ吉２（）。??情形２当坏的４〇－面上出现２个５＋－点的时候，５－面上各有一个５＋－点且该５＋－点不??与４。－面上的点相邻时是最坏的，此时／Ａ：Ｔ）仝ｍＣＯ?＋?８ｘ｜?＋?４ｘｆ?＋?２ｘｉ＞０。??情形３当坏的４Ｑ－面上出现１个４－点和１个５＋－点的时候，５－面上各有一个??４－点和５＋－点且该４－点和５＋－点不与４０－面上的点相邻时是最坏的，此时／／（乃２??＂（Ｔ）?＋?８ｘ｜?＋?４ｘ．?＋?ｌｘ｜?＋?２ｘ咅仝０。而且我们还可以得到，这三种情形下，??情形〗是最终权值最小的一个，且不低于〇。?口??弓丨理４．４．如果：Ｔ是Ｉ?—?５－面和它上面的８个顶点导出的子图，則Ｗ）?２?〇。??证明：由引理３．４的（１）、（２）、（３）和（４），?４！?—?５－面至
本文编号：3496816
本文链接：https://www.wllwen.com/kejilunwen/yysx/3496816.html
