共查询到20条相似文献,搜索用时 421 毫秒
1.
2.
如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果. 相似文献
3.
4.
5.
给出了平面图为第一类图的边数的一些上界,并给出了平面图为第一类图的一些充分条件. 相似文献
6.
7.
极大外平面图在边界条件下的4染色 总被引:6,自引:0,他引:6
本文利用极大外平面图的对象变换研究它的染色,并给出了特征向量的概念,证明了任意两上有公共界环的极大外平面图都可以通过一系列对角变换互相得到,进而证明了有公共标定界环的两个极大外平面图在某些条件下有公共4染色。 相似文献
8.
图的星色数的概念是Vince在1988年提出的,它是图的色数的一个推广.本文构造了一类星色数是4的平面图. 相似文献
9.
In this paper we show that the face-width of any embedding of a Halin graph(a type of planar graph) in the torus is one, and give a formula for determining the number of all nonequivalent embeddings of a Halin graph in the torus. 相似文献
10.
Moo Young SOHN Sang Bum KIM Young Soo KWON Rong Quan FENG 《数学学报(英文版)》2007,23(3):411-416
In the present paper, the regular planar graphs with diameter two are classified. 相似文献
12.
13.
给出了平面图的一个结构性定理,并证明了每个没有5-圈,相邻三角形,相邻四边形的平面图是(3,1)*-可选色的. 相似文献
14.
冯纪先 《数学的实践与认识》2005,35(1):106-111
对简单完整正则平面图的特性和结构进行了分析和讨论 ,找出了简单完整正则平面图的可能的种类 .此外 ,对各种简单完整正则平面图的色数进行了求解 ,并用不同的方法给出了各个简单完整正则平面图的作色方案 . 相似文献
15.
给出了平面图的一个结构性定理,并证明了每个没有5-圈,相邻三角形,相邻四边形的平面图是(3,1)*-可选色的. 相似文献
16.
Bao-gangXu 《应用数学学报(英文版)》2004,20(4):597-604
In this paper, we prove that if G is a plane graph without 4-, 5- and 7-circuits and without intersecting triangles, then for each face f of degree at most 11, any 3-coloring of the boundary of f can be extended to G. This gives a positive support to a conjecture of Borodin and Raspaud which claims that each plane graph without 5-circuits and intersecting triangles is 3-colorable. 相似文献
17.
Bao Gang XU 《数学学报(英文版)》2007,23(6):1059-1062
In this paper, we prove that every plane graph without 5-circuits and without triangles of distance less than 3 is 3-colorable. This improves the main result of Borodin and Raspaud [Borodin, O. V., Raspaud, A.: A sufficient condition for planar graphs to be 3-colorable. Journal of Combinatorial Theory, Ser. B, 88, 17-27 (2003)], and provides a new upper bound to their conjecture. 相似文献
18.
19.
朱晓颖 《纯粹数学与应用数学》2013,(6):609-614
寻找平面图是3-或者4-可选择的充分条件是图的染色理论中一个重要研究课题,本文研究了围长至少是4的特殊平面图的选择数,通过权转移的方法证明了每个围长至少是4且不合8-圈,9-圈和10-圈的平面图是3-可选择的. 相似文献
20.
可平面图完备色数唯一性问题赵克文(华南师范大学数学系,广州510631)我们已经知道,图的点色数、边色数,点边金色数X_T都是唯一的。那么,可平面图的边面完备色数X唯一吗 ̄[2]?本文对此有结论:并非每一可平面图的完备色数都唯一,由此就产生问题:X(... 相似文献