【摘要】：本文主要研究的是簡單有限圖.圖的點染色是對圖G的頂點集的一種剖分.如果圖G的頂點集V可以剖分成互不相交的k部分,給每一部分染上同一種顏色,不同部分所染的顏色不同,若剖分產(chǎn)生的各部分都是點獨立集,則圖G是正常點染色.若圖G存在一個頂點集到顏色集的映射φ:V(G)-→{1,2,···,k},對于G中的任意兩個相鄰的點u和v,φ(u)?=φ(v),則稱φ是圖G的一個k染色又稱圖G是k-可染的.圖的色數(shù)是指一個圖正常點染色所用的最少顏色數(shù).一個圖被稱為1-平面圖當(dāng)且僅當(dāng)它可以畫在一個平面上,使得它的任何一條邊最多交叉另外一條邊.1986年,Borodin在[14]中證明了1-平面圖是6-可染的.2005年,1-平面圖是否是4-可染的被證明是NP-完備的.2016年,宋立莉在[10]中證明不含4-圈以及5-點不與5-點相鄰的1-平面圖是5-可染的.本文共分三章,主要討論的是加了某些限制條件的1-平面圖的正常點染色問題.在第一章中,主要介紹了論文所涉及的有關(guān)概念和符號以及本文的研究背景和已有的一些結(jié)果.在第二章、第三章中將平面圖的正常點染色研究推廣到了1-平面圖的正常點染色研究,證明了:圍長至少是5的1-平面圖是5-可染的.不含4-圈5-圈和6-圈的1-平面圖是5-可染的.
[Abstract]:In this paper, we mainly study simple finite graphs. The vertex coloring of a graph is a partition of the vertex set of a graph G. If the vertex set V of graph G can be divided into disjoint k-parts and each part is dyed with the same color, the different parts are dyed differently. If each part produced by the partition is a vertex independent set, then G is normal point coloring. For any two adjacent points u and v in G, 蠁 (u) = 蠁 (v), is called a k-coloring of graph G and a graph G is k-dyeable if there exists a mapping from the vertex set to the color set 蠁: v: v (G)-{1 (G) 2, k}. For any two adjacent points u and v in G, 蠁 (u) G = 蠁 (v), is called a k-coloring of graph G. The chromatic number of a graph is the minimum number of colors used for the normal point coloring of a graph. A graph is called a 1-planar graph if and only if it can be drawn on a plane. In 1986, Borodin proved in [14] that a 1-plane graph is 6-dyed. Whether a 1-plane graph is 4-dyed in 2005 is proved to be NP-complete. In [10], Song Lili proved that 1- planar graphs without 4cycles and 5- points not adjacent to 5- points are 5- dyeable. This paper is divided into three chapters. We mainly discuss the normal point coloring of 1-planar graphs with some restricted conditions. In the first chapter, we mainly introduce the related concepts and symbols, the research background and some results. In chapter 2, in chapter 3, the normal point coloring of planar graphs is extended to the normal point coloring of 1-planar graphs. It is proved that 1-planar graphs with a girth of at least 5 are 5-dyeable. A 1-planar graph that does not contain 4-cycles 5-cycles and 6-cycles is 5-dyeable.
【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【參考文獻(xiàn)】

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

1 張欣;劉桂真;吳建良;;1-平面圖的結(jié)構(gòu)性質(zhì)及其在無圈邊染色上的應(yīng)用[J];中國科學(xué):數(shù)學(xué);2010年10期

2 張欣;劉桂真;吳建良;;不含3-圈的1-平面圖的邊染色[J];山東大學(xué)學(xué)報(理學(xué)版);2010年06期

3 ;Planar graphs without 4,6,8-cycles are 3-colorable[J];Science in China(Series A:Mathematics);2007年11期

4 ;A 3-color Theorem on Plane Graphs without 5-circuits[J];Acta Mathematica Sinica(English Series);2007年06期

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

1 宋立莉;某些特殊圖的點染色問題研究[D];山東師范大學(xué);2016年

，

本文編號：2185273