不含4-圈和三角化6-圈的环面图森林分解

A forest partition of toroidal graphs with[JZ]neither 4-cycles nor triangular 6-cycles

假设G是一个有限简单图.令V(G)和E(G)分别表示图G的点集合和边集合.若能将G的点集合V(G)划分为2个不交的子集合V_(1)和V_(2),使得由V_(1)和V_(2)导出的子图满足G[V_(1)]是森林且G[V_(2)]是最大度至多为d的森林,则称G有一个(F,F_(d))-分解.运用反证法,通过对极小反例的结构分析,找到可约构形,再通过权转移讨论证明:不含4-圈和三角化6-圈的环面图有(F,F_(3))-分解.

It was studied a finite simple graph G with vertex set V(G)and edge set E(G).An(F,F_(d))-parti-tion was introduced for G while V(G)could be divided into two disjoint subsets V_(1)and V_(2)such that G[V_(1)]constructed a forest and G[V_(2)]also constructed a forest with maximum degree at most d.Based on the method of proof by contradiction,some useful reducible configurations were obtained by analyzing the structure of min-imal counterexamples,and then argued by an appropriate discharging method.It was finally proved that every toroidal graph with neither 4-cycles and triangular 6-cycles admitted an(F,F_(3))-partition.