期刊信息
- 刊名： 河北师范大学学报（自然科学版）Journal of Hebei Normal University (Natural Science)
- 主办： 河北师范大学
- ISSN： 1000-5854
- CN： 13-1061/N
- 中国科技核心期刊
- 中国期刊方阵入选期刊
- 中国高校优秀科技期刊
- 华北优秀期刊
- 河北省优秀科技期刊
不含4圈图的森林分解
-
1. 河北师范大学 数学与信息科学学院, 河北 石家庄 050024;
2. 福州大学 离散数学研究中心, 福建 福州 350003 -
DOI：10.11826/j.issn.1000-5854.2014.01.003
Forests Decomposition of Graphs Without 4-cycles
摘要/Abstract
摘要：
研究了不含4圈图的森林分解问题.利用权转移法，得到了任意一个不含4圈的NC图能分解成2个森林和1个线性森林.
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.
参考文献 4
- [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.