位置:成果数据库 > 期刊 > 期刊详情页
关于平面图点荫度的一点改进
  • ISSN号:0469-5097
  • 期刊名称:《南京大学学报:自然科学版》
  • 时间:0
  • 分类:O157.5[理学—数学;理学—基础数学]
  • 作者机构:[1]南京师范大学数学与计算机科学学院,南京210097
  • 相关基金:National Natural Science Foundation of China (10371055).Acknowledgments The authors extend their appreciation to the referees for their many useful and wise suggestions, which resulted in an improved paper.
中文摘要:

一个非平凡图G的点荫度a(G)是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林.近年来对点荫度的研究成为图论的一个焦点并且关于这个问题有更深一步的发展,例如,随机图的点荫度以分式点荫度等.得到一个关于平面图的点荫度的一个上界;如果平面图G是没有3-圈,或是没有4-圈,或是没有5-圈,那么G的点荫度不超过2.研究的起因是一个著名的猜想:任何3-可着色的平面图的点荫度不超过2.四色定理是图论中最著名的一个定理,伴随产生了一个问题,那就是什么样的平面图是3-可着色的.不幸,这是一个难问题,Garey等人证明了判定一个平面图是否3-可着的即使在一个点不超过4的条件下仍然是NP-难问题.因此这个猜想是一个不易解决的,人们开始在一些特殊图上进行验证这个猜想是否正确.我们知道一个著名的定理:不含3-圈的平面图是3-可着色的.结合结果,给出猜想的一个正面的肯定.Havel给出两个反例,如果平面图含有4-圈或有5-圈是不可3-可着色的,因此4-圈和5-圈在证明平面图是3-可着色时必须排除.不过在结论中,如果平面图不含有4-圈或不含有5-圈,那么它的点荫度不超过2.从而可以看出猜想的条件还是很强的.同时我们的结果也拓宽了张忠辅等人的结果:外平图的点荫度不超过2.

英文摘要:

The vertex arboricity a(G) of a nonempty graph G is the minimum number of subsets into which the vertex set V (G) can be partitioned so that each subset induces a subgraph that is a forest. The research on the vertex arboricity of a graph G becomes a focus field as well as many extended branches on the graph theory in the past years, such as the vertex arboticity on random graph and fractional arboricity etc. This paper provides an upper bound for a(G) of a connected nonempty plane graph G, namely a(G) 42 where G is a plane graph without/-cycles for some i∈{3, 4, 5}. The work is concerned with a famous conjecture which says that every 3-colorable plane graph has the vertex arboricity which is no more than 2. The famous 4-coloring theorem produces a new problem: what kind of plane graphs is 3- colorable. But this problem is NP-hard even for a given plane graph with a degree not exceeding 4 is 3-colorable or not (Garey et al , 1976, Theoretical Computer Science, 1:237-267). So the conjecture is hard to solve. Therefore, people have to find some special graphs to identify the conjecture. It is well known that every triangle-free plane graph is 3-colorable. Thus, the conjecture holds if G is a plane graph with triangle-free. In Havel (1969, Journal of Combinatorial Theory, 7:184-186), Havel provided that both 4-cycles and 5-cycles must be excluded to ensure that the plane graphs are 3-colorable. But in our theorem, if a plane graph G is either 4-cycle-free or 5-cycle-free, then a(G) ≤2. The conjecture's condition is stronger. And our results improve the conclusion on a(G) ≤ 2 for outer plane graph(Zhang and Wang , 1991, Mathematical Applicata, 4(2) : 14-18).

同期刊论文项目
同项目期刊论文
期刊信息
  • 《南京大学学报:自然科学版》
  • 中国科技核心期刊
  • 主管单位:中华人民共和国教育部
  • 主办单位:南京大学
  • 主编:龚昌德
  • 地址:南京汉口路22号南京大学(自然科学版)编辑部
  • 邮编:210093
  • 邮箱:xbnse@netra.nju.edu.cn
  • 电话:025-83592704
  • 国际标准刊号:ISSN:0469-5097
  • 国内统一刊号:ISSN:32-1169/N
  • 邮发代号:28-25
  • 获奖情况:
  • 中国自然科学核心期刊,中国期刊方阵“双效”期刊
  • 国内外数据库收录:
  • 美国化学文摘(网络版),美国数学评论(网络版),德国数学文摘,中国中国科技核心期刊,中国北大核心期刊(2004版),中国北大核心期刊(2008版),中国北大核心期刊(2011版),中国北大核心期刊(2014版),中国北大核心期刊(2000版)
  • 被引量:9316