Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ l (G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ l (G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known theorem of Ohba for list chromatic number, we obtain ρ l (G + K n ) = ρ(G + K n ) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ l (G) = ρ(G). Particularly, we determine that rl(K2(n))=éfrac 2n3ùrho_l(K_{2(n)})=lceil frac {2n}{3}rceil, where K 2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if r(G) ³ frac n 3rho(G)geq frac {n} {3} then ρ l (G) = ρ(G).
展开▼
机译：令G为简单图形。 G的点树状度ρ（G）定义为G的点集的分区中子集的最小数量，以便每个子集都可以诱发一个无环子图。列表点的树状度ρ l （G）是最小值k，因此对于| L（v）|的G的任何列表分配L，都存在非循环L色。 ≥k。因此，任意图G的ρ（G）≤ρ l （G）。Xue和Wu证明了二部图的列表点任意性可以任意大。作为对表色数的Ohba著名定理的一个类似式，我们获得ρ l （G + K n ）=ρ（G + K n ），当n足够大时，对于任何固定图G。结果，如果ρ（G）足够接近G中顶点数量的一半，则ρ l （G）=ρ（G）。特别是，我们确定r l （K 2（n））=éfrac2n3ùrho_l（K_ {2（n）}）= lceil frac {2n} {3} rceil ，其中K 2（n）是完整的n个局部图，每个局部集正好包含两个顶点。我们还推测，对于具有n个顶点的图G，如果r（G）³frac n 3rho（G）geq frac {n} {3}，则ρ l （G）=ρ（G） 。
展开▼
