平面图的(F, F_d)-分解问题

Vertex Partitions of Graphs into a Forest and a Forest with Bounded Maximum Degree

图G的(F, Fd)-分解是指将G的顶点集合划分为两个子集F和Fd,使得G[F]为森林,G[Fd]为最大度至多为d的森林。本文证明了每一个不含4-圈和5-圈的平面图都存在(F, Fd)-分解。

An(F,Fd)-partition of a graph G is a vertex partition of its vertex set into subsets F and Fd such that G[F]is a forest,while G[Fd]is a forest of maximum degree at most d.In this paper,we prove that every planar graph without 4-cycles and 5-cycles admits an(F,Fd)-partition.