一类无短圈环面图的顶点森林分解问题

Vertex forest partitioning problem of toroidal graphs without short cycles

令G=(V,E)是一个图.G的一个(F,Fd)-分解是指将G的顶点集合V分解为2个子集合V1和V2,使得子图G[V1]是森林,G[V2]是最大度至多为d的森林.通过对极小反例图进行结构分析,并利用权转移方法证明:不含4-圈和6-圈的环面图有(F,F3)-分解.

It was considered a kind of graph G=(V,E)with its vertices could be partitioned into two subsets V1 and V2 such that G[V1]was a forest and G[V2]was a forest with bounded maximum degree at most d,such a partition was called an(F,Fd)-partition of G.By analyzing structure properties of the minimum counterexample,together with discharging method,it was proved that every toroidal graph with neither 4-cycles nor 6-cycles admited an(F,F3)-partition.