平面图和1-平面图的若干染色问题

发布时间：2018-05-19 22:18

  本文选题：无圈列表染色 + 边染色　； 参考：《山东大学》2017年博士论文

【摘要】：图的染色问题是图论领域中一个经典而且比较活跃的分支.图的染色问题已由传统的边染色、点染色和全染色发展为种类繁多的新型染色问题,每种染色都有着各自重要的理论价值和适当的应用背景.这些新型染色问题在算法设计、时间排序问题以及资源分配问题中有着广泛的应用,这不仅产生了许多有趣的未解决问题,而且也促使研究方法不断创新,从而极大地丰富了图的染色理论.本文主要研究平面图和1-平面图的无圈列表(点)染色、正常边染色、正常全染色、(p,1)-全染色以及邻点可区别全染色问题.除非特殊说明,约定本文中所涉及到的图均为有限、无向、简单且非空的图.给定图G,用V(G),E(G),△(G)分别表示图G的顶点集,边集和最大度.v(G)=|V(G)|和e(G)= |E(G)|分别表示G的阶数和边数.图G的围长是G中最短圈的长度,记为g(G).如果一个圈除了自身以外它相邻一个3-圈,则称此圈为三角化的;如果一个圈除了自身以外它相邻一个4-圈,则称此圈为四角化的.平面图是指能够嵌入到平面上使得其任意两条边仅在端点处相交的图,这样的嵌入称为平面嵌入,该平面嵌入称为平图.1-平面图G是指G能够嵌入到平面上使得G的任意一条边最多被交叉一次.1-平面图G按照上述条件的一种画法称为G的一种1-平面嵌入,此1-平面嵌入称为1-平图.所以1-平图中的每个交叉点ω都是由两条边相交所得,从而每个交叉点ω都对应着两条相交边,同时也对应着由这两条相交边的四个端点组成的集合ψ(ω).如果1-平面图的一个1-平面嵌入中任意两个交叉点ω和ω'满足ψ(ω)nψ(ω')=(?),则称此1-平面图为IC-平面图.给定图G =(V(G),E(G)),它的正常k-点染色是指一个映射φ:V(G)→{1,2,…,k},使得图G中任意两个相邻的顶点u和满足φ(u)≠ φ(v).使得G具有正常k-点染色的最小正整数k称为G的点色数,记为χ(G).在图G的一个正常点染色φ中,如果G中的每个圈上至少有三种颜色,则称φ为图G的无圈染色.如果给图G的每个顶点v ∈ V(G)都分配一个颜色集合L(v),则称L={L(v:v V ∈ }为G的一个点列表.给定点列表L,如果G中存在无圈染色φ使得每个顶点v的颜色满足φ(v)∈L(v)则称图G是无圈L-可染的.如果对任意点列表L,图G是无圈L-可染的,其中对任意点v ∈ V(G)有|L(v)|≥ k,则称图G是无圈k-可选的.使得图G是无圈k-可选的最小正整数k称为G的无圈列表色数,记为χal(G).Borodin等人猜想:每个平面图都是无圈5-可选的.我们主要讨论具有相邻3-圈的平面图是无圈5-可选或者无圈6-可选的充分条件.图G的一个正常k-边染色是一个映射φ:E(G)→ {1,2,…,k},使得任意两条相邻的边x,y ∈ E(G)满足φ(x)≠φ(y).使得G具有正常k-边染色的最小正整数k称为图G的边色数,记为χ'(G).著名Vizing定理证明每个简单图G的边色数χ'(G)要么等于最大度△(G)要么等于△(G)+1。这个定理将所有的图分成了两类:第一类图满足关系式χ'(G= △(G),第二类图满足关系式χ'(G)= △(G)+ 1.如果连通图G是第二类图,并且对G中的任意边e有不等式χ'(G-e)χ'(G)成立,则称G是临界图.如果G是最大度为△的临界图,则称G为△-临界图.张欣和吴建良证明了每个最大度至少为10的1-平面图是第一类的.同时,张欣构造了最大度为6或7的第二类的1-平面图,随后张欣和刘桂真提出了猜想:每个最大度至少为8的1-平面图都是第一类的.我们证明了最大度至少为8的1-平面图和最大度至少为7的IC-平面图在限制弦圈的条件下是第一类的.图G的一个正常l-全染色是一个映射φ:V(G)∪ E(G){1,2,…,k},使得任意两个相邻或关联的元素x,y∈V(G)∪E(G)满足φ(x)≠φ(y).使得G具有正常k-全染色的最小正整数k称为图G的全色数,记为χ"(G).Behzad与Vizing分别独立地提出了著名的全染色猜想:任意简单图G满足≤ △(G)+ 2.根据1-平面图的结构特点和附加结构特征,我们分别确定了最大度至少为9和最大度至少为12的1-平面图在围长的限制条件下的全色数的上界.图G的k-(p,1)-全染色是从V(G)∪ E(G)到颜色集合{0,1,…,k}的映射φ,使得图G中相邻或相关联的元素满足以下条件:当uv ∈ E(G)时,|φ(u)-φ(v)| ≥ 1;当边e1和边e2相邻时,|φ(e1)-φ(e2)| ≥ 1;当顶点u和边e关联时,|φ(u)-φ(e)}≥p.使得图G有k-(p,1)-全染色的最小正整数k称为图G的(p,1)-全色数,记为λpT(G).Havet和Yu提出了(p,1)-全染色猜想:任何图G满足λpT(G)≤ min{△(G)+ 2p-1,2△(G)+ p-1}.通过分析结构性质,我们得到最大度至少为4p+4的平面图和最大度至少为6p +3的特殊1-平面图的(p,1)-全色数的上界.在图G的一个正常k-全染色φ中,令Cφ(v)表示顶点v的颜色及与其关联的边的颜色集合.如果图G中的任意一条边uv满足Cφ(u)≠Cφ(v),则称这个正常k-全染色φ为邻点可区别k-全染色.使得G具有邻点可区别k-全染色的最小正整数k称为图G的邻点可区别全色数,记为χa"(G).关于邻点可区别全染色,张忠辅等人提出以下猜想:阶数至少是2的任意图G有χa"(G)≤ △(G)+3.我们将应用代数工具"组合零点定理"研究图的结构,从而得出对于△(G)≥ 8的特殊平面图G,以上猜想成立.为了详细清晰地阐述本文的主要结果,我们将论文分为五章.第一章首先介绍图论中相关的基本术语和定义,然后详细叙述所要研究的图类的基本结构和染色问题的定义、猜想以及目前的发展状况,最后列出本文的主要结论.第二章主要讨论平面图的无圈列表染色.重点是局部调整某些顶点的颜色从而讨论相应问题的图结构,最后得出主要结论.我们证明了如果平面图G不含5-圈和相邻4-圈,并且G中的任意一个顶点v至多关联一个j-圈,j ∈ {6,7},则G是无圈5-可选的.另外,我们还证明了如果平面图G既不含三角化的5-圈也不含四角化的k-圈,其中,k∈ {4,5},则G是无圈6-可选的.第三章主要研究1-平面图的边染色问题.通过观察分析△-临界图的结构特点,我们证明了以下两个结论:如果1-平面图G的最大度至少为8且图G中的每个5-圈至多含一条弦,则G是第一类的;如果IC-平面图G的最大度至少为7且图G不含相邻弦6-圈,则G是第一类的.第四章主要研究平面图和1-平面图的正常全染色、(p,1)-全染色以及邻点可区别全染色.首先,对于正常全染色,通过分析1-平面图的结构特点,我们证明了以下结论:△(G)≥ 9 且 g(G)≥ 4 的 1-平面图 G 满足 χ"(G)≤ △(G)+ 2;△(G)≥ 12且g(G)≥ 5的1-平面图G满足χ"(G)≤ △(G)+1.其次,对于(p,1)-全染色问题,p ≥ 2,我们证明了 △(G)≥4p+ 4的平面图G和△(G)≥ 6p+3且不含相邻三角形的1-平面图G的(p,1)-全色数均至多为△(G)+ 2p-2.最后,对于邻点可区别全染色,我们证明了 △(G)≥ 8且不含相邻4-圈的平面图G满足χa"(G)≤ △(G)+3.第五章主要提出了现阶段正在研究的问题,并指出今后研究工作中几个可行的研究思路和方法.
[Abstract]:In this paper , we have shown that G can be embedded in the plane so that any two edges of G can be embedded in the plane so that any two edges of G can be embedded in the plane . Let G be an acyclic k - optional minimum positive integer k called G . If there is no circle in G , it is called 蠂 ' ( G ) . Let G have a minimum positive integer k of normal k - total coloring , called the total chromatic number of graph G . It is known as 蠂 " ( G ) . The best degree of G is equal to 鈮，

本文编号：1911930