在线阅读 --自然科学版 2014年1期《不含4圈图的森林分解》
不含4圈图的森林分解--[在线阅读]
王涛1, 吴丽霞2
1. 河北师范大学 数学与信息科学学院, 河北 石家庄 050024;
2. 福州大学 离散数学研究中心, 福建 福州 350003
起止页码: 10--13页
DOI: 10.11826/j.issn.1000-5854.2014.01.003
摘要
研究了不含4圈图的森林分解问题.利用权转移法,得到了任意一个不含4圈的NC图能分解成2个森林和1个线性森林.
关键字: NC图 4圈 欧拉示性数

Forests Decomposition of Graphs Without 4-cycles
WANG Tao1, WU Lixia2
1. College of Mathematics and Information Sciences, Hebei Normal University, Hebei Shijiazhuang 050024, China;
2. Center for Discrete Mathematics, Fuzhou University, Fujian Fuzhou 350003, China
Abstract:
A decomposition of a graph G consists of edge-disjoint subgraphs with union G.We show that every NC-graph without 4-cycles can be decomposed into two forests and a linear forest.

收稿日期: 2013-4-15
基金项目: 国家自然科学基金(11201113,11271108)

参考文献:
[1]BONDY J A,MURTY U S R.Graph Theory [M].Berlin:Springer,2010.
[2]GONCALVES D.Covering Planar Graphs with Forests,One Having Bounded Maximumdegree [J].J Combine Theory Ser B,2002,99:314-322.
[3]HE W,HOU X,LIH K W,et al.Edge-partitions of Planar Graphs and Their Game Co-loring Numbers [J].J Graph Theory,2002,41:307-317.
[4]BORODIN O V,IVANOVA A O,KOSTOCHKA A V,et al.Decompositions of Quanrangle-free Planar Graphs [J].Discussions Mathematic Graph Theory,2009,29:87-99.