论文标题
顶点分区分为一个独立的集合和一个森林，每个组成部分小
Vertex Partitions into an Independent Set and a Forest with Each Component Small
论文作者
论文摘要
对于每个整数k> = 2，我们确定对疯狂（g）的尖锐绑定，以便可以将v（g）划分为i和f_k集，其中i是一个独立的集合，g [f_k]是每个组件在最多具有k个顶点的森林。对于每个K，我们构建了一个无限的例子，显示我们的结果是最好的。我们的结果表明，每个平面图G的每个平面图至少9（分别为8，7）都将V（g）分配到独立的集合I和A集合中，使G [F]是一个最多有秩序的森林，最多3（resp。4，6）。 亨德里（Hendrey），诺林（Norin）和伍德（Wood）要求最大的函数g（a，b），以便如果疯狂（g）<g（a，b），那么v（g）将a和b分配为a和b，以使得疯狂（g [a]）<a和mad（g [b]）<b。他们特别要求G（1，b）的值，即A是独立集的情况。以前，唯一已知的值是G（1,4/3）和G（1,2）。每当4/3 <b <2时，我们都会发现g（1，b）。
For each integer k >= 2, we determine a sharp bound on mad(G) such that V(G) can be partitioned into sets I and F_k, where I is an independent set and G[F_k] is a forest in which each component has at most k vertices. For each k we construct an infinite family of examples showing our result is best possible. Our results imply that every planar graph G of girth at least 9 (resp. 8, 7) has a partition of V(G) into an independent set I and a set F such that G[F] is a forest with each component of order at most 3 (resp. 4, 6). Hendrey, Norin, and Wood asked for the largest function g(a,b) such that if mad(G) < g(a,b) then V(G) has a partition into sets A and B such that mad(G[A]) < a and mad(G[B]) < b. They specifically asked for the value of g(1,b), i.e., the case when A is an independent set. Previously, the only values known were g(1,4/3) and g(1,2). We find g(1,b) whenever 4/3 < b < 2.
