本文選題：點染色 + 邊染色　； 參考：《山東大學(xué)》2016年博士論文

【摘要】：一百多年前,四色問題的提出成為圖論發(fā)展史上的一個里程碑,它開創(chuàng)了圖論的一個重要分支,即圖的染色理論.圖的染色理論無論是在日常生活中還是理論研究中都有著非常重要的應(yīng)用.圖的染色理論又有多個分支,本文主要研究兩類具有某些限制條件的圖的染色問題.即邊染色和兀圈邊染色.在這篇文章中,我們探討的圖都是簡單無向的有限非空圖.假設(shè)G是一個圖.我們把圖G的頂點集.邊集,最小度數(shù),最大度數(shù),圍長分別用V(G),E(G),δ(G),△(G).g(G)(或簡單的用V，E,巧.△,g)來表示.膏-圈是指長度為k的圈.給定G的一個圈C,其長度為矗.如果x,y是圈C上的頂點且ry∈E(G)\E(C),那么這條邊叫做C的一條弦.圈C稱為含弦κ-圈.兩個圈稱為相鄰的,如果這兩個圈至少關(guān)聯(lián)一條共同的邊.在本文中,我們主要研究了平面圖和1-平面圖的染色問題.可平面圖是能夠映射在-個平面上使得該圖的任意兩條邊僅在端點處相交.滿足以上條件的映射叫做圖G的平面嵌入.可平面圖的這種平面映射方式,叫做平面圖.我們把平面圖G的面的集合用F(G)來表示.如果一個圖G映射在平面上能夠使得每條邊至多與其它一條邊交叉,這個圖就叫做1-平面圖.在這篇文章中,我們解決某些圖的染色問題主要是運用的是權(quán)轉(zhuǎn)移方法.這個方法是研究圖論問題的重要工具之一,其作用尤其體現(xiàn)在研究平面圖的結(jié)構(gòu)和染色上.這篇文章的難點在于賦值規(guī)則的制定.首先,我們制定出一個大體的權(quán)轉(zhuǎn)移方向使得圖G的大多數(shù)頂點和面的權(quán)值在經(jīng)過重新分配后得到的權(quán)值是大于或等于0的.然后,我們根據(jù)實際情況,對某些權(quán)值仍然小于0的頂點制定一個特別的賦值規(guī)則.這些頂點的新權(quán)值可能來自于度數(shù)比自己小的某些鄰點,也可能來自鄰點的鄰點.最后.我們通過檢驗可證明制定的賦值規(guī)則是符合要求的.給定圖G=(V, E),它的一個κ-邊染色,是指圖G的關(guān)于邊集合E的一個映射妒：E→{1,2,…,忍}.正常的邊染色是指給圖G的每條邊涂上顏色后,該圖的每兩條有公共頂點的邊所涂的顏色都互不相同.如果有一個正常的邊染色能夠用尼種顏色把圖G的每條邊涂完,那么圖G是κ-邊可染的.在圖G的所有正常邊染色中,所需顏色最少的那個邊染色用到的顏色數(shù)叫做G的邊色數(shù),記為x’(G).關(guān)于邊染色問題,1964年,Vizing證明了：如果圖G是一個簡單圖,則△≤χ'(G)≤△+1這個定理后來被叫做Vizing定理.其將所有簡單圖分類如下：邊色數(shù)等于其最大度數(shù)的圖G屬于第1類的,邊色數(shù)等于其最大度數(shù)加1的圖G屬于第2類的.本文由四個部分組成.第一章是對整篇文章的一個大體介紹.在第1小節(jié)中,我們給出了所用到的一些定義和符號.在第2小節(jié)中.我們簡單地介紹了本文所研究的兩類染色問題,即圖的邊染色和無圈邊染色.在第3小節(jié)中,我們詳細(xì)地介紹了本文所用的研究方法-權(quán)轉(zhuǎn)移方法,并給出具體例子來說明此方法的具體操作步驟.在第4小節(jié)中,我們列出了本文所得到的主要結(jié)論.在第二章中,首先我們介紹了平面圖的邊染色研究現(xiàn)狀,即對于平面圖的邊染色,現(xiàn)在只剩下最大度數(shù)為6的情況還沒能確定是否屬于第1類.但是對某些有局部條件的情形,已經(jīng)有了若干結(jié)果.隨后我們給出了證明過程中所用到的若干重要引理.最后我們分四個小節(jié),詳細(xì)的展示了我們所得到的關(guān)于△≥6的平面圖的邊染色的四個結(jié)論.本章的四個結(jié)論如下：結(jié)論1.如果G中每個6-圈不超過三條弦,那么G是第1類的.結(jié)論2.如果G中每個7-圈不超過三條弦,那么G是第1類的.結(jié)論3.如果G中每兩個7-圈都互不相鄰,那么G是第1類的.結(jié)論4.如果G中每兩個8-圈都互不相鄰,那么G是第1類的.在第三章中,首先我們介紹了1-平面圖的研究現(xiàn)狀及其多種染色,然后對其邊染色進(jìn)行了研究.1-平面圖的邊染色問題是由張欣和吳建良首次提出,并且他們證明了每個最大度數(shù)大于等于10的1-平面圖是第1類的.此外他們還構(gòu)造出了最大度數(shù)為6或7的第2類1-平面圖并且提出下面的猜想：每個最大度數(shù)至少是8的1-平面圖是第1類的.到目前為止,對于1-平面圖的邊染色,最大度數(shù)為8和9的情況都還沒能確定是否屬于第1類.但是對某些有限制條件的情況.已經(jīng)有了幾個結(jié)果.在本章中.我們也是利用權(quán)轉(zhuǎn)移方法來研究某些1-平面圖的邊染色.首先,我們需要對1-平面圖G進(jìn)行一個操作：把G嵌入到一個平面內(nèi).使得每條邊至多被其它邊交叉一次且交叉點的數(shù)目達(dá)到最小.我們將G的所有交叉點看作新的4-度點,這樣得到的圖就是一個平面圖.我們把這個圖叫做G的伴隨平面圖,記作Gx.然后,我們對G的伴隨平面圖Gx運用權(quán)轉(zhuǎn)移方法來得到一個矛盾,從而完成證明.在本章的第2,3,4小節(jié)中.我們得到了關(guān)于1-平面圖的邊染色的三個結(jié)果：結(jié)論5.假設(shè)G是一個△≥8的1-平面圖.如果G中每兩個4-圈都互不相鄰,那么G是第1類的.結(jié)論6.假設(shè)G是一個△≥8的1-平面圖.如果G中沒有5-圈,那么G是第1類的.結(jié)論7.假設(shè)G是一個△≥9的1-平面圖.如果G中每兩個帶弦5-圈都互不相鄰.那么G是第1類的.最后,在本文的第四章,我們還探討了平面圖的無圈邊染色.這章分為兩小節(jié).在第1小節(jié)中,我們介紹了無圈邊染色的定義及其研究現(xiàn)狀.給定圖G的一個正常的邊染色.如果G中一個圈的邊僅涂兩種顏色.那么這個圈叫做雙色圈.在圖G的正常的邊染色中,如果存在一個邊染色使得G中不會出現(xiàn)雙色圈,那么這個邊染色叫做圖G的無圈邊染色.如果有一個正常的無圈邊染色能夠用斥種顏色把圖G的每條邊涂完,那么圖G是無圈邊κ-可染的.在圖G的所有正常無圈邊染色中,所需顏色最少的那個無圈邊染色用到的顏色數(shù)叫做G的無圈邊色數(shù),記為a’(G).圖的無圈邊染色猜想是由Alon,Sudakov與Zaks在2001年提出的,其內(nèi)容為：對于任意的圖G.a'(G)≤△(G)+2目前,這個猜想被證明對某些特殊圖是成立的.另外,對某些有限制條件的平面圖這個猜想也是成立的.第2小節(jié)是這章結(jié)論的證明部分.我們在證明過程中,對平面圖G進(jìn)行了一個操作：刪掉其所有的2-度點,得到一個子圖H.然后對H運用權(quán)轉(zhuǎn)移方法,得出矛盾.從而完成證明.我們得到關(guān)于無圈邊染色猜想的結(jié)果如下：結(jié)論8.假設(shè)G是一個平面圖.如果對每個頂點v,都有一個整數(shù)k,∈{3,4,5}使得v不關(guān)聯(lián)任意的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.).

【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張埂;吳樹猛;焦嬌;;最大度為4的圖的無圈邊染色[J];青島科技大學(xué)學(xué)報(自然科學(xué)版);2011年02期

2 陳光;侯建鋒;;不含三角形的輪胎圖的無圈邊染色[J];山東大學(xué)學(xué)報(理學(xué)版);2014年04期

3 陳艷君;田雙亮;;特殊積圖的無圈邊染色[J];襄樊學(xué)院學(xué)報;2012年05期

4 孫向勇;吳建良;;一些平面圖的無圈邊染色[J];山東大學(xué)學(xué)報(理學(xué)版);2008年09期

5 吳燕青;謝德政;趙燦鳥;;不含5-圈的平面圖的無圈邊著色[J];純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué);2012年03期

6 段娟娟;丁偉;周菲;;不含相交三角形和4圈的平面圖的無圈邊染色[J];蘇州科技學(xué)院學(xué)報(自然科學(xué)版);2012年02期

7 楊文娟;謝德政;;平面圖無圈邊著色的一個結(jié)果[J];重慶工商大學(xué)學(xué)報(自然科學(xué)版);2012年04期

8 丁偉;;不含4圈的平面圖的無圈邊染色[J];山東大學(xué)學(xué)報(理學(xué)版);2012年06期

9 張埂;;不含短圈平面圖的無圈邊染色的一個結(jié)果[J];貴州師范學(xué)院學(xué)報;2012年06期

10 張埂;;不含3,4圈的平面圖的無圈邊染色的一個結(jié)果[J];貴州師范大學(xué)學(xué)報(自然科學(xué)版);2014年01期

相關(guān)重要報紙文章 前1條

1 蔣宇冰;一圈邊紙值幾個錢[N];中國商報;2005年

相關(guān)博士學(xué)位論文 前2條

1 張文文;兩類圖的邊染色與無圈邊染色[D];山東大學(xué);2016年

2 舒巧君;圖的無圈邊染色[D];蘇州大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 謝衛(wèi)強;一些圖的圈邊分解數(shù)[D];陜西師范大學(xué);2001年

2 包雙寶;一些積圖和方體圖的圈邊分解數(shù)[D];內(nèi)蒙古工業(yè)大學(xué);2005年

3 鄭麗娜;若干圖的無圈邊染色[D];浙江師范大學(xué);2012年

4 盛平;平面圖的無圈邊染色[D];浙江師范大學(xué);2012年

5 陳艷君;若干圖的無圈邊染色[D];西北民族大學(xué);2012年

6 孫興建;關(guān)于平面圖的無圈邊染色的研究[D];中國礦業(yè)大學(xué);2014年

7 舒巧君;平面圖的無圈邊染色[D];浙江師范大學(xué);2011年

8 張亞瓊;平面圖無圈邊著色指數(shù)的新界[D];河南大學(xué);2014年

9 楊威;最大度較大的平面圖的無圈邊染色[D];福州大學(xué);2011年

10 吳燕青;關(guān)于平面圖的兩種著色[D];重慶大學(xué);2011年

，

本文編號：1789016