List Point Arboricity of Dense Graphs |
| |
Authors: | Lingyan Zhen Baoyindureng Wu |
| |
Institution: | (1) College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang, 830046, P.R. China |
| |
Abstract: | 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 , 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 then ρ
l
(G) = ρ(G).
Research supported by NSFC (No.10601044) and XJEDU2006S05. |
| |
Keywords: | List coloring Point arboricity List point arboricity |
本文献已被 SpringerLink 等数据库收录! |
|