平面图的列表点（边、全）染色和列表线性荫度
发布时间：2018-03-02 10:26
本文关键词： 全染色 列表染色 邻和可区别的全染色 列表线性荫度 出处：《山东大学》2017年博士论文 论文类型：学位论文
【摘要】：图论最早源于著名的哥尼斯堡七桥问题,已有两百多年的发展史.图的染色理论起源于四色问题,是图论研究中最重要的课题之一.在自然科学、社会科学领域都有重要的应用.在本论文中,我们研究了图的全染色、列表染色、邻和可区别全染色和列表线性荫度的问题.若无特别明确指出,本文所考虑的都是简单的,无向的,有限的和非空的图.令G =(V,E)是一个图,对一个点v∈V(G),用NG(v)表示v在图G中的邻点集,dG(v)= |NG(v)|是点v的度数.图G的最大度和最小度分别用Δ(G)和δ(G)表示.为方便起见,令Δ = Δ(G)和δ = δ(G).图G的kk-全染色是指用k种颜色(1,2,…,k)对V(G)∪E(G)中的元素进行染色,使得相邻的两个元素或者相关联的两个元素染不同的颜色.图G的所有k-全染色中的最小正整数k称为G的全色数,记为χ"(G).关于图的全染色猜想(Total Coloring Conjecture):对任意图 G,Δ + 1 ≤ χ"(G)≤Δ+ 2.这个猜想对于△ ≤ 5的一般图都成立.随着研究的不断深入,研究者发现有很多图的全色数不只满足全染色猜想,还可以取到相应的下界,也就是说χ"(G)= Δ + 1.就平面图而言,对△ = 6的平面图全染色猜想还未证明成立.而对△ ≥ 9的平面图G,已经证明了 χ"(G)= Δ + 1.对4≤Δ≤8的平面图,也未找到不能(Δ+1)-全可染的例子.于是有了平面图猜想:任意最大度至少为4的平面图是(△ +1)-全可染的.本文在第二章证明了平面图的全染色的三个相关结果:(1)对于△ ≥ 8的平面图G,若任何两个弦6-圈不相邻或者任意6-圈至多只含一条弦,则χ"(G)= △ + 1;(2)对于△ ≥ 8的平面图G,若任何7-圈至多含两条弦,则χ"(G)= Δ + 1;(3)对于△ ≥ 7的平面图G,若任何两个弦5-圈不相交,则χ"(G)= △ + 1.一个映射L被称为图G的一个分配,如果对于每个点v ∈ V(G),都有一个列表L(v).如果G存在一种染色使得每个点从列表中得到颜色,并且每两个相邻的点颜色不同,我们称G是L-点可染的.称图G是kk-点可选的,如果|L(v)| ≥ kk且G是点可染的,这里v是G中的任意一个点.我们在第三章证明了平面图G中3-圈或4-圈不同时与5-圈相邻,G是4-可选的.如果对于图G的任意一条边e ∈E(G),我们给其一个颜色集合L(e),那么就称L为G的一个边列表.对于图G的任意一个满足条件|L(e)| ≥k的边列表L,其中e ∈E(G)为G的任意一条边,如果G都是L-边可染的,那么就称图G是k-边可选的.使图G是kk-边可选的最小正整数k称为图G的列表边色数,记作χ"(G).类似地,我们可以给出图G的列表全色数χl"(G)的定义,即把上述边染色换为对图的顶点和边进行染色.在第三章我们证明了对于平面图G,若最大度Δ(G)8,且4-圈与5-圈不相邻,则χl'(G)= Δ,χl"(G)+ 1;若最大度Δ(G)≥ 6,且4-圈与5-圈不相邻,则χl'(G)= Δ + 1,χl"(G)= Δ + 2.近年来,魔幻、反魔幻标号、非正则强度等与"和(sum)"有关的染色与标号问题引起了广泛关注,其中比较著名的有1-2-3猜想和1-2猜想.本文的第四章给出图的邻和可区别全染色的定义,并给出相关问题的一些猜想和主要研究进展.用f(v表示点v及所有与其关联的边的颜色的加和,如果对任意的边uv,有f(u)≠ f(v)，则称这样的kk-全染色为图G的k-邻和可区别全染色.k的最小值称为图G的邻和可区别全色数,定义为χ∑"(G).Pilsniak和Wozniak猜想对至少两个顶点的图G,χ∑" ≤ △(G)+ 3.目前这个猜想已经证明对于完全图,圈,二部图,立方图,系列平行图和△ ≥ 14的平面图都成立.我们证明了对于可嵌入到欧拉示性数非负曲面的图来说,χ∑"(G)≤ max{Δ(G)+ 2,16}.最后,本文还讨论了平面图的列表线性荫度.一个图G的线性荫度是指把图G中的边集剖分成线性森林的最小数目,记为la(G).Akiyama等人猜想kα(G)≤[Δ(G)+1/2]对每个正则图G都成立.显然,对于每个图G都有la(G)≥[Δ(G)/2],对于每个正则图G都有la(G)≥[Δ(G)+1/2],因此,Akiyama等人的猜想等价于如下猜想,即线性荫度猜想:设G是一个简单图,则[Δ(G)/2]kα(G)「Δ(G)+1/2].如果对于图G的任意一条边e ∈ E(G),我们给其一个颜色集合L(e)(?)N,那么就称L为G的一个边列表,其中N是一个正整数集合.如果G存在一个正常的边染色φ(e)使得对每条边e有φ(e)∈ L(e)且对任意的i ∈ Cφ有(V(G),φ-1(i),其中Gφ = {φ(e)|e ∈E(G)}.那么我们说G是线性L-可染的且φ是G的线性的L-染色.我们说G是线性k-可选的如果G是线性L-可染的且对于所有边e的每个列表分配L满足|L(e)|≥ k.一个图G的列表线性荫度lalist(G)定义为G是线性kk-列表可染的最小值k.显然la(G)≤lalist(G).本文的第五章,我们证明了如果G是一个平面图且G中7-圈至多含两条弦,那么若Δ(G)≥ 6,则G是线性[Δ+1/2]-可选的,若Δ(G)11,则G是线性[[Δ/2]-可选的.在本文的第六章,我们将对全文进行总结,并提出在图的染色问题中一些今后可继续研究的课题.
[Abstract]:鍥捐鏈，
本文编号：1556136
本文链接：https://www.wllwen.com/shoufeilunwen/jckxbs/1556136.html
教材专著
