1-平面图正常点染色问题的研究
发布时间：2018-08-16 07:30
【摘要】：本文主要研究的是简单有限图.图的点染色是对图G的顶点集的一种剖分.如果图G的顶点集V可以剖分成互不相交的k部分,给每一部分染上同一种颜色,不同部分所染的颜色不同,若剖分产生的各部分都是点独立集,则图G是正常点染色.若图G存在一个顶点集到颜色集的映射φ:V(G)-→{1,2,···,k},对于G中的任意两个相邻的点u和v,φ(u)?=φ(v),则称φ是图G的一个k染色又称图G是k-可染的.图的色数是指一个图正常点染色所用的最少颜色数.一个图被称为1-平面图当且仅当它可以画在一个平面上,使得它的任何一条边最多交叉另外一条边.1986年,Borodin在[14]中证明了1-平面图是6-可染的.2005年,1-平面图是否是4-可染的被证明是NP-完备的.2016年,宋立莉在[10]中证明不含4-圈以及5-点不与5-点相邻的1-平面图是5-可染的.本文共分三章,主要讨论的是加了某些限制条件的1-平面图的正常点染色问题.在第一章中,主要介绍了论文所涉及的有关概念和符号以及本文的研究背景和已有的一些结果.在第二章、第三章中将平面图的正常点染色研究推广到了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.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
本文编号：2185273
[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.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
【参考文献】
相关期刊论文 前4条
1 张欣;刘桂真;吴建良;;1-平面图的结构性质及其在无圈边染色上的应用[J];中国科学:数学;2010年10期
2 张欣;刘桂真;吴建良;;不含3-圈的1-平面图的边染色[J];山东大学学报(理学版);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期
相关硕士学位论文 前1条
1 宋立莉;某些特殊图的点染色问题研究[D];山东师范大学;2016年
，本文编号：2185273
本文链接：https://www.wllwen.com/kejilunwen/yysx/2185273.html
