平面图的邻和可区别全染色和邻和可区别列表全染色

发布时间：2018-04-03 00:13

  本文选题：平面图　切入点：邻和可区别全染色　出处：《中国矿业大学》2017年硕士论文

【摘要】：令G = (V(G),E(G))是一个图,k是一个正整数. G的一个k-全染色是一个映射φ: V(G) ∪ E(G)→{1,2,..., k},且同时满足以下三个条件:(1).对G中任意一对相邻的顶点u,v,φ(u)≠φ(v);(2).对G中任意一对相邻的边e, e',φ(e)≠φ(e');(3).对G中任意的顶点v,和与v关联的边e,φ(u)≠φ(e).令f(v)表示与顶点v关联的所有边的颜色加上顶点v的颜色的和.图G的一个k-全染色,如果同时满足对G中任意的一条边uv,都有f(u)≠f(v),则称为G的k-邻和可区别全染色,满足这些染色条件的最小的k-值称为G的邻和可区别全色数,记为χtnsd"(G).给G的每一个顶点和边z ∈ V∪E都分配一个颜色列表Lz,如果对每一个z∈ V∪E,都可以从其对应的列表Lz中选择一种颜色对其进行染色,使得G中存在一个邻和可区别全染色,则称G是邻和可区别L-列表全可染的,如果对G中的每一个列表L = {Lz||Lz≥ k,z ∈ V∪E}, G都是邻和可区别L-列表全可染的,则称最小的k-值为G的邻和可区别全可选择数,记为chtnsd"(G).关于图的邻和可区别全染色,Pil'sniak和Wo'zniak提出如下猜想:对任意的简单图G,χtnsd"(G)≤△(G)+3.这个猜想已经被证明了对于完全图,圈,二分图和子立方图都成立.同时通过比较定义可得:χtnsd"(G)≤chtnsd"(G),因此很多文章开始研究对任意的平面图χtnsd"(G)≤△(G)+3.是否也成立.本文主要利用反证法,组合零点定理,权转移方法证明了关于平面图的邻和可区别全染色和邻和可区别列表全染色的两个结论,文章一共分为4章.第1章主要介绍本文的研究背景,相关符号和定义,邻和可区别全染色和邻和可区别列表全染色及其他相关染色的研究现状.第2章通过分析不含4-圈且△ ≥ 9的平面图的结构,证明了:对于△ ≥ 9且不含4-圈的平面图,χtnsd"(G) ≤ △(G) + 2.第3章通过分析不含带弦5-圈且△ ≥ 8的平面图的结构,证明了:对于△ ≥8且不含带弦5-圈的平面图,chtnsd"(G)≤△(G)+3.根据χtnsd"(G)≤chtnsd"(G),因此第三章得到的结论对于邻和可区别全染色同样成立.第4章总结和展望.
[Abstract]:Let G = G = a graph K is a positive integer.A k-total coloring of G is a mapping 蠁: v _ (G) Karabakh E _ (G) {1 ~ (2) ~ (2) ~ (...., k}), and satisfies the following three conditions: (1) ~ (1) ~ (-1) at the same time.For any pair of adjacent vertices in G, u, 蠁 v) 鈮，

本文编号：1702750