List Vertex-arboricity Of Graphs

The vertex-arboricity of a graph G is the minimum number of subsets into which the set of vertices of G can be partitioned so that each subset induces a forest. A forest k-coloring of a graph G is a mapping φ:V(G) â†'{1,2,..., k}, such that each color class induces a forest. The vertex-arboricity a(G), is the least integer k such that G has a forest k-coloring.If G has a forest coloring Ï€, such that Ï€(x) ∈ L(x) for each v ∈ V(G), then we say that G is forest L-colorable. If, for any list L satisfying |L(x)|≥ k for each v ∈ V(G), G is forest L-colorable, then G is ca_lled forest k-choosable. The list vertex-arboricity a_l(G) is the least integer k such that G is forest k-choosable.The vertex-arboricity of a graph was first introduced by Chartrand, Kronk and Wa_ll(1968), named by point-arboricity. At the same time, they proved that a(G)< [â–³+1/2], and the vertex-arboricity of planar graphs is at most 3. Raspaud and Wang(2008), and Huang, Shiu and Wang(2012) proved that every planar graph G without k-cycles for some fixed k∈{3,4,5,6,7} has a(G)≤ 2. In 2012, Chen, Raspaud and Wang proved a conjecture by Raspaud and Wang(2008) which says that a(G)≤ 2 if G is a planar graph without intersecting triangles. A natura_l question is:every planar graph G without intersecting k-cycles, for some fixed k ∈{4,5,6,7}, has (list) vertex-arboricity at most 2?Borodin and Ivanova proved that every planar graph G without 4-cycles adjacent to 3-cycles has a_l(G)≤ 2. Is it a_lso ture for toroida_l graphs?In this master thesis, we study the list vertex-arboricity of plane graphs and toroida_l graphs. The thesis consists of three chapters.In Chapter 1, we collect some basic notations, give a chief survey in this direction and state the main results obtained.In Chapter 2, we study the list vertex-arboricity of toroida_l graphs and obtain the following three results:(1) Every toroida_l graph G without 3-cycles adjacent to 5-cycles has a_l(G)≤ 2.(2) Every toroida_l graph G without 4-cycles adjacent to 5-cycles has a_l(G)≤ 2.(3) Every toroida_l graph G without 3-cycles adjacent to 4-cycles has a_l(G)≤2.In Chapter 3, we study the list vertex-arbor icity of plane graphs by showing that every planar graph G without intersecting 5-cycles has a_l;(G)≤ 2.