平面图有一个严格f-退化染色的一些充分条件

发布时间：2021-06-25 00:25

　　染色是图论的一个重要分支,而图论这门学科最初诞生于著名的哥尼斯堡七桥问题,以图为研究对象.图的染色问题一直是图论界的一个热门话题,它起源于1852年由Guthrie提出的“四色猜想”.随着图论这门学科的发展,后来Vizing提出了点染色的列表形式,列表点染色是点染色的推广.2015年,Dvo?ák和Postle提出了关于列表点染色的一般形式,简称为DP-染色.在这之前及其期间,还有一些其他的染色被陆续提出来,比如图的点荫度问题,图的退化问题,等等.2018年,T.Wang提出了关于图的严格f-退化染色问题,简称为SFDT.严格f-退化染色是以上所有染色的更一般形式,这具有很大的研究意义.通过研究点荫度,DP-染色和退化问题的相关论文,来更好的学习和研究图的SFDT问题.能否把图的相关染色推广到SFDT上,及图G是否有一个SFDT是一个值得研究的问题.本论文主要研究平面图及环面图的严格f-退化染色问题,分为五个章节.第一章是一些基本术语及符号定义,还有一些相关的定理.第二章给出了与严格f-退化染色相关的结论.第三章我们给出的结果是没有一些小的子图的环面图有一个严格f-退化染色,它是许多已... 

【文章来源】：河南大学河南省

【文章页数】：38 页

【学位级别】：硕士

【部分图文】：

定理2.2.2里的递归点对

另一个可约结构

平面图有一个严格f-退化染色的一些充分条件μ′(v)≥64232×133×215>0.因此，v不能是任何4-正则的5-面的悬挂点.根据引理3.2.3，v不可能同时给剩余三个邻接5+-面权23，所以μ′(v)>643×23=0.情形7.设v是一个7+-点.根据给权规则，v平均给每个邻接的面权最多13，因此μ′(v)≥d(v)4d(v)×13>0.图3.3:情形8里的一些子情形情形8.设v是一个5-点，那么▽(v)≤3.如果▽(v)=3且f1,f2和f4都是3-面，那么f3和f5都是6+-面，因此v最多分别给f3和f5权13，通过f4-面给出去权215，因此μ′(v)=542152×13>0.如果v邻接两个3-面f1和f2，那么f3和f5一定都是6+-面，因此μ′(v)=54>0.如果▽(v)=1，那么μ′(v)=542152×13>0.如果▽(v)=0，那么μ′(v)=54>0.接下来，假设v邻接两个不相邻的3-面，不妨假设是f1和f3.情形8.1.假设f2不是一个F5-面.那么很容易推出f2是一个5-面最多相邻四个3-面，或者5-面上有至少两个5+-邻点，或者是一个6+-面.根据规则R4和R5，v最多给f2权13.如果v5是一个5+-点，那么v最多分别给f4和f5权16，因此μ′(v)≥54132×162×215>0.如果v5是一个4-点，那么f4或者f5是一个-面，因此μ′(v)≥542×132×215>0.情形8.2.假设f2是一个F5-面.根据引理3.3.1，v不可能是任何一个4-正则的5-面的悬挂点.根据引理3.2.1，f4和f5都不可能是（5，4，4，4，4）-面.情形8.2.1.v5是一个4-点，那么f4或者f5是一个-面，不然就会出现图1.2(b)禁止的结构，矛盾.当f4或者f5是一个-面时，v是不给它权的.如果v给了f4或者f5一个正权，那么这个面一定是一个5-面且至少有两个5+-邻点，那么v最多给f4或者f5权4312=16，因此μ′(v)≥542316>0.18


本文编号：3248116