两类图的边染色与无圈边染色

发布时间：2018-04-22 21:25

本文选题：点染色 + 边染色　；参考：《山东大学》2016年博士论文

【摘要】：一百多年前,四色问题的提出成为图论发展史上的一个里程碑,它开创了图论的一个重要分支,即图的染色理论.图的染色理论无论是在日常生活中还是理论研究中都有着非常重要的应用.图的染色理论又有多个分支,本文主要研究两类具有某些限制条件的图的染色问题.即边染色和兀圈边染色.在这篇文章中,我们探讨的图都是简单无向的有限非空图.假设G是一个图.我们把图G的顶点集.边集,最小度数,最大度数,围长分别用V(G),E(G),δ(G),△(G).g(G)(或简单的用V，E,巧.△,g)来表示.膏-圈是指长度为k的圈.给定G的一个圈C,其长度为矗.如果x,y是圈C上的顶点且ry∈E(G)\E(C),那么这条边叫做C的一条弦.圈C称为含弦κ-圈.两个圈称为相邻的,如果这两个圈至少关联一条共同的边.在本文中,我们主要研究了平面图和1-平面图的染色问题.可平面图是能够映射在-个平面上使得该图的任意两条边仅在端点处相交.满足以上条件的映射叫做图G的平面嵌入.可平面图的这种平面映射方式,叫做平面图.我们把平面图G的面的集合用F(G)来表示.如果一个图G映射在平面上能够使得每条边至多与其它一条边交叉,这个图就叫做1-平面图.在这篇文章中,我们解决某些图的染色问题主要是运用的是权转移方法.这个方法是研究图论问题的重要工具之一,其作用尤其体现在研究平面图的结构和染色上.这篇文章的难点在于赋值规则的制定.首先,我们制定出一个大体的权转移方向使得图G的大多数顶点和面的权值在经过重新分配后得到的权值是大于或等于0的.然后,我们根据实际情况,对某些权值仍然小于0的顶点制定一个特别的赋值规则.这些顶点的新权值可能来自于度数比自己小的某些邻点,也可能来自邻点的邻点.最后.我们通过检验可证明制定的赋值规则是符合要求的.给定图G=(V, E),它的一个κ-边染色,是指图G的关于边集合E的一个映射妒：E→{1,2,…,忍}.正常的边染色是指给图G的每条边涂上颜色后,该图的每两条有公共顶点的边所涂的颜色都互不相同.如果有一个正常的边染色能够用尼种颜色把图G的每条边涂完,那么图G是κ-边可染的.在图G的所有正常边染色中,所需颜色最少的那个边染色用到的颜色数叫做G的边色数,记为x’(G).关于边染色问题,1964年,Vizing证明了：如果图G是一个简单图,则△≤χ'(G)≤△+1这个定理后来被叫做Vizing定理.其将所有简单图分类如下：边色数等于其最大度数的图G属于第1类的,边色数等于其最大度数加1的图G属于第2类的.本文由四个部分组成.第一章是对整篇文章的一个大体介绍.在第1小节中,我们给出了所用到的一些定义和符号.在第2小节中.我们简单地介绍了本文所研究的两类染色问题,即图的边染色和无圈边染色.在第3小节中,我们详细地介绍了本文所用的研究方法-权转移方法,并给出具体例子来说明此方法的具体操作步骤.在第4小节中,我们列出了本文所得到的主要结论.在第二章中,首先我们介绍了平面图的边染色研究现状,即对于平面图的边染色,现在只剩下最大度数为6的情况还没能确定是否属于第1类.但是对某些有局部条件的情形,已经有了若干结果.随后我们给出了证明过程中所用到的若干重要引理.最后我们分四个小节,详细的展示了我们所得到的关于△≥6的平面图的边染色的四个结论.本章的四个结论如下：结论1.如果G中每个6-圈不超过三条弦,那么G是第1类的.结论2.如果G中每个7-圈不超过三条弦,那么G是第1类的.结论3.如果G中每两个7-圈都互不相邻,那么G是第1类的.结论4.如果G中每两个8-圈都互不相邻,那么G是第1类的.在第三章中,首先我们介绍了1-平面图的研究现状及其多种染色,然后对其边染色进行了研究.1-平面图的边染色问题是由张欣和吴建良首次提出,并且他们证明了每个最大度数大于等于10的1-平面图是第1类的.此外他们还构造出了最大度数为6或7的第2类1-平面图并且提出下面的猜想：每个最大度数至少是8的1-平面图是第1类的.到目前为止,对于1-平面图的边染色,最大度数为8和9的情况都还没能确定是否属于第1类.但是对某些有限制条件的情况.已经有了几个结果.在本章中.我们也是利用权转移方法来研究某些1-平面图的边染色.首先,我们需要对1-平面图G进行一个操作：把G嵌入到一个平面内.使得每条边至多被其它边交叉一次且交叉点的数目达到最小.我们将G的所有交叉点看作新的4-度点,这样得到的图就是一个平面图.我们把这个图叫做G的伴随平面图,记作Gx.然后,我们对G的伴随平面图Gx运用权转移方法来得到一个矛盾,从而完成证明.在本章的第2,3,4小节中.我们得到了关于1-平面图的边染色的三个结果：结论5.假设G是一个△≥8的1-平面图.如果G中每两个4-圈都互不相邻,那么G是第1类的.结论6.假设G是一个△≥8的1-平面图.如果G中没有5-圈,那么G是第1类的.结论7.假设G是一个△≥9的1-平面图.如果G中每两个带弦5-圈都互不相邻.那么G是第1类的.最后,在本文的第四章,我们还探讨了平面图的无圈边染色.这章分为两小节.在第1小节中,我们介绍了无圈边染色的定义及其研究现状.给定图G的一个正常的边染色.如果G中一个圈的边仅涂两种颜色.那么这个圈叫做双色圈.在图G的正常的边染色中,如果存在一个边染色使得G中不会出现双色圈,那么这个边染色叫做图G的无圈边染色.如果有一个正常的无圈边染色能够用斥种颜色把图G的每条边涂完,那么图G是无圈边κ-可染的.在图G的所有正常无圈边染色中,所需颜色最少的那个无圈边染色用到的颜色数叫做G的无圈边色数,记为a’(G).图的无圈边染色猜想是由Alon,Sudakov与Zaks在2001年提出的,其内容为：对于任意的图G.a'(G)≤△(G)+2目前,这个猜想被证明对某些特殊图是成立的.另外,对某些有限制条件的平面图这个猜想也是成立的.第2小节是这章结论的证明部分.我们在证明过程中,对平面图G进行了一个操作：删掉其所有的2-度点,得到一个子图H.然后对H运用权转移方法,得出矛盾.从而完成证明.我们得到关于无圈边染色猜想的结果如下：结论8.假设G是一个平面图.如果对每个顶点v,都有一个整数k,∈{3,4,5}使得v不关联任意的kv-圈,那么a'(G)≤△(G)+2.
[Abstract]:More than 100 years ago, the presentation of the four color problem became a milestone in the history of graph theory. It created an important branch of graph theory, that is, the theory of graph dyeing. The theory of dyeing is very important in both daily life and theoretical research. The color theory of graph has many branches, this paper mainly studies two The dyed problem of a graph with some restricted conditions. That is edge coloring and edge coloring. In this article, we discuss a simple and undirected finite non empty graph. Suppose G is a graph. We take the vertex set of the graph G, the set, the minimum degree, the maximum degree, and the circumference, respectively, using V (G), E (G), Delta (G), Delta (G).G (G), or simple V, E, ingenious. The length of a circle of G is K. If x, y is the vertex of the circle C and ry E (G) E (C), then this edge is called a string. The circle is called the chord kappa - ring. The two cycles are called adjacent, if the two circles are at least a common side. In this article, we mainly studied flat. The problem of dyeing of surface and 1- plane graphs. A plane graph is a map that can be mapped on a plane to make the two edges of the graph intersected only at the end point. The mapping of the above conditions is called the plane embedding of graph G. The plane mapping method of the plane graph is called a plane map. We use the F (G) to represent the set of the flat surface of the plane graph G. A graph G can be mapped on a plane to make every edge cross to the other side at most. This graph is called 1- plane graph. In this article, we solve some graph coloring problems mainly using the right transfer method. This method is one of the most important tools for the study of graph theory, and its function is especially reflected in the study of graphic drawings. Structure and dyeing. The difficulty of this article lies in the formulation of the assignment rule. First, we make a general direction of weight transfer so that the weight value of most vertex and surface of graph G is greater than or equal to 0 after redistribution. Then, according to the actual situation, we have a vertex system that is still less than 0 of the weight value. Set a special assignment rule. The new weights of these vertices may come from some neighbour points smaller than themselves or neighbour points. Finally, we can prove that the rule of assignment is consistent with the requirement. Given the given graph G= (V, E), it is a kappa edge coloring, which refers to a mapping jealousy of graph G on the edge set E. E - {1,2,... A normal edge coloring refers to the color of each side of the graph G. The color of every two common vertex sides of the graph is different. If a normal edge coloring can be painted with the color of each edge of the graph G, then the graph G is kappa side dyeable. In all normal edge coloring of figure G, the required color is least. The number of colors used in that edge coloring is called the edge color number of G, which is called X '(G). On the edge coloring problem, in 1964, Vizing proved that if graph G is a simple graph, then the theorem of delta X' (G) < < Delta +1 is later called the Vizing theorem. All simple graphs are classified as follows: the graph G with the edge color number equal to its maximum degree belongs to the first class. The graph G with the edge color equal to its maximum degree plus 1 plus 1 belongs to the second class. This article is made up of four parts. The first chapter is a general introduction to the whole article. In the first section, we give some definitions and symbols used. In the second section, we briefly introduce the two class of dyeing problems, that is, the edge coloring of the graph. In the third section, we introduce the method of weight transfer in detail in this paper, and give specific examples to illustrate the specific operation steps of this method. In the fourth section, we list the main conclusions obtained in this article. In the second chapter, we first introduce the status of edge dyeing research in Plane Graphs. For the edge coloring of a plane graph, there is only a maximum degree of 6 left to the first class. But for some local conditions, there are some results. Then we give some important lemmas used in the process of proof. Finally, we divide four sections to show what we get in detail. Four conclusions on the edge coloring of a plane graph with delta > 6. The four conclusions of this chapter are as follows: conclusion 1. if each 6- circle in G does not exceed three strings, then G is the first class. Conclusion 2. if each 7- circle in G is not more than three strings, then G is first. Conclusion G is first if each of the two 7- cycles in G is not adjacent to each other. 4. if every two 8- cycles in G are not adjacent to each other, then G is of the first class. In the third chapter, we first introduce the status of the study of the 1- plane and a variety of coloring, and then the edge coloring problem for its edge dyeing is studied by Zhang Xin and Wu Jianliang for the first time, and they prove that each maximum degree is greater than equal to equal. 10 of the 1- plane maps are of the first class. In addition, they have constructed a second class 1- plan with a maximum degree of 6 or 7 and proposed the following conjecture: each maximum degree of at least 8 of the 1- plane is first. To date, the case for the edge dyeing of the 1- plane, the maximum degree of 8 and 9 has not yet been determined to belong to the first class. However, there have been several results for some restricted conditions. In this chapter, we also use the weight transfer method to study the edge coloring of some 1- plane graphs. First, we need to do an operation on the 1- plane map G: embedding G into a plane. We look at all the intersection points of the G as a new 4- degree point, so that the graph is a plane graph. We call this graph a graph of the adjoint plane of G, as Gx., and then we get a contradiction by using the right transfer method of the adjoint plane graph Gx of G, which is proved. In the 2,3,4 section of this chapter, we get it. Three results about edge coloring on 1- plane graphs: conclusion 5. assumes that G is a 1- plane graph of delta 8. If every two 4- circles in G are not adjacent to each other, G is the first class. Conclusion 6. assumes that G is a 1- plane graph of delta > 8. If there are no 5- cycles in G, then G is the first class. Every two band 5- rings are not adjacent to each other. Then G is the first class. Finally, in the fourth chapter of this article, we also discuss the ring free edge coloring of the plane graph. This chapter is divided into two sections. In the first section, we introduce the definition of the ring free coloring and its research status. Given a normal edge coloring of graph G. If the edge of a circle in G is only the edges of the graph, the edge of a circle is only the edge of the graph. Two colors are painted. Then this ring is called a double color ring. In the normal edge coloring of figure G, if there is an edge coloring that makes G not a double color ring, then the edge coloring is called the ring free edge coloring of figure G. If a normal ring free edge coloring can be painted with seed colors for each edge of the graph G, then G is a ring - free K - kappa - Dyeable. In all normal ring free edge coloring of figure G, the least colored edge coloring is called the ring free edge color number called G, which is called a '(G). The ring free edge coloring conjecture is proposed by Alon, Sudakov and Zaks in 2001. The content is that this conjecture is proved to be available to arbitrary graph G.a' (G) < Delta (G)) +2. This conjecture is proved The second section is a proof of the conclusion of this chapter. In the process of proving, we do an operation on the plane graph G: delete all of its 2- points, get a subgraph H. and apply the right transfer method to H, and draw a contradiction. So we get the proof. We get the result of the ring free edge coloring conjecture as follows: conclusion 8. assumes that G is a plane graph. If every vertex v has an integer k, {3,4,5} makes V unrelated to any kv- circle, then A'(G) < Delta (G) +2.).

【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】