图的点荫度与点线性荫度.pptVIP

图的点荫度和点线性荫度 马刚 山东大学数学院 The vertex arboricity va(G) of a graph G is the minimum number of colors that can be used to color the vertices of G so that each color class induces a forest of G. The vertex linear arboricity vla(G) of a graph G is the minimum number of colors that can be used to color the vertices of G so that each color class induces linear forest of G. For any graph G, Theorem (Kronk and Mitchem, 1975) Let G be a simple connected graph. If G neither a cycle nor a clique of odd order, then Theorem (Matsumoto,1990) Let G be a connected graph. Then (1)There exists a coloring of G such that each induced subgraph has only or as its connected components. (2) . (3)If for some positive integer n, then if and only if G is a cycle or . Theorem (Akiyama, Era, Gervacio and Wtanabe, 1989) If G is a graph with maximum degree d, then Theorem (Catlin and Lai, 1995) Let k be a natural number and let G be a connected simple graph with that is not a complete graph (if ) nor a cycle (if k=1). Then and there is a k-coloring of G such that each color class induces a forest, and such that one color class is a maximum induced forest in G. Theorem (Catlin and Lai, 1995) Let G be a connected simple graph ,and let k be a positive integer, then G has a (k+1)-coloring ,where each color class is a forest .Further more ,if G is not a complete graph then for each property below, this coloring can be chosen to satisfy that property: (a) one color class is edgeless and one color class may be assumed to be a maximum induced forest, or (b) one color class may be assumed to be a maximum independent set. Theorem (Burr, 1986) For every graph G, . Moreover, for every , there is a G with va(G)=a(G)=k. Theorem (Michem 1970) Let G be any graph of o