图的邻和可区别边染色和邻和可区别全染色

发布时间：2018-04-14 22:22

本文选题：正常边染色 + 正常全染色　；参考：《中国矿业大学》2017年硕士论文

【摘要】：对于图(7)EVG,(8),给定一个正整数k,一个正常k边染色是一个映射c?{.....2,1:kE},对于任意两条相互关联的边?(7)GE(8)21e,e,有(7)(8)(7)(8)21ecec1。一个正常k全染色是一个映射V?{.....2,1:kEc}U,使得每一对相邻的点和相邻的边以及相关联的点和边所对应的值不一样。设c是G的一个正常边染色,对(7)GV(8)中任意一点v,令?(7)vc(8)代表与v相关联的边的颜色之和,如果对(7)GE(8)中的每条边uv,有(7)(8)?1?(7)vcuc(8),那么这样一个正常边染色叫做邻和可区别边染色,满足这种染色的最小k值叫做邻和可区别边色数,用(7)G(8)?c￠来表示。类似地对于图(7)EVG,(8)的正常全染色,对于(7)GV(8)中任意一点v,令?(7)vs(8)代表与v相关联的边的颜色与点v的颜色之和。如果对(7)GE(8)中的每条边uv,有(7)(8)?1?(7)vsus(8),那么这样一个正常全染色叫做邻和可区别全染色。满足这种染色的最小k值叫做邻和可区别全色数,用(7)G(8)?c￠来表示。本文主要证明了两个定理,第一个定理,对于不含孤立边的简单图G,如果(7)Gmad(8)(27)310,那么￠(7)(8)kG￡?c,其中,k{(10)(35)(28)14,2max}。第二个定理,对于平面图G,如果(7)G(8)3(35)5且(7)Gg(8)35,那么￠(7)(8)(7)(8)(10)(35)￡3?cGG。本文主要内容具体分为四章展开:第一章,介绍研究领域的相关背景及本文用到的基本概念和研究现状。第二章,利用欧拉公式及权转移规方法证明了第一个定理。第三章,利用权转移法规则构造反例证明了第二个定理。第四章,对本文的结果进行了简单的总结并作了进一步的展望。
[Abstract]:Given a positive integer k, a normal k-edge coloring is a mapping? {....2n 1: KE}, and for any two interrelated edges, there is a positive integer k, a normal k-edge coloring is a map c {.....2n 1: KE}, and for any two interrelated edges, there is a positive integer k, a normal k-edge coloring is a map c {.......A normal k-total coloring is a mapping V {{.....2n 1: KEC} U, such that each pair of adjacent points and adjacent edges and the associated points and edges correspond to different values.Let c be a normal edge coloring of G, so that any point vin 7 / GV) so that the sum of the colors of the edges associated with v is represented, if for each edge UV in 7 / G / 8) there is a 7 / 7 / 7 / v cuc8s, then such a normal edge dyeing is called adjacent and distinguishable edge dyeing.The minimum k value satisfying this kind of coloring is called the adjacent and differentiable edge chromatic number, which is expressed in the form of 7 ~ (7) G ~ (+) ~ (8) C.Similarly, for the normal total coloring of fig. 7 / EVGG), for any point of v8), such a v8) represents the sum of the color of the edge associated with v and the color of the dot v.If for each edge UV, there is a normal total dyeing called adjacent and distinguishable total dyeing.The minimum k value satisfying this kind of coloring is called adjacent and distinguishable total chromatic number, which is expressed in terms of 7 ~ (7) G ~ (+) ~ ((8)) C.In this paper, we mainly prove two theorems. The first theorem is that for a simple graph G with no isolated edges, if the graph G is 7 / 7 / G / 8 / 27 / 310, then 7 / 7 / 8 / 8kG / c, in which k {10 / 10 / 35 / 28 / 14 / 2max}.The second theorem is that for the planar graph G, if there are 7g ~ (8) ~ 3 ~ ~ ~ (5) and ~ ~ (7) G ~ (g) ~ (8) ~ ~ ~ (35), then there is no _ _ _The main contents of this paper are divided into four chapters: the first chapter introduces the relevant background of the research field, the basic concepts used in this paper and the current research situation.In chapter 2, the first theorem is proved by using Euler formula and weight transfer gauge method.In chapter 3, the second theorem is proved by using the rule of weight transfer to construct counterexample.In the fourth chapter, the results of this paper are summarized and further prospects are given.
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】