关于图的全荫度和列表全荫度的一些结果

图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ"(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度硝(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图‰,ρ"(Kn)=「(n+1)/2];(2)对完全二部图Kn,n,ρ"(Kn,n)=「(n+2)/2];(3)对Halin图G,ρl"(G)≤「(△(G)+2)/2].

SOME RESULTS ON TOTAL ARBORICITY AND LIST TOTAL ARBORICITY OF GRAPHS

The total graph T(G) of G is the graph with vertex set V(G)UE(G),where two vertices are adjacent in T(G) if and only if they correspond to adjacent or incident elements in G.The total arboricity ρ"(G) of a graph G is the smallest number of subsets into which V(T(G)) can be partitioned so that each subset induces a forest in the total graph.The list total arboricity ρl"(G) is the list coloring version of this concept.In this paper,it is proved that:(1) for any complete graph Kn,ρ"(Kn) =(n + 1)/2];(2) for any complete bipartite graph Kn,n,ρ"(Kn,n) =(n + 2)/2];(3) for any Halin graph G,ρl"(G) ≤ (Δ(G) + 2)/2].