List Coloring And Listddvertex-arboricity Of Planar Graphs

Let G be a simple graph.A proper k-coloring of a graph G is a mapping φ:V(G)→｛1,2,…k} such that every edge xy ∈ E(G),satisfies φ(x)≠φ(y).The chromatic number,denoted by x(G),of a graph G is the smallest positive integer k such that G has a proper k-coloring.Let L={L(v)| v ∈ V(G)} be a list assignment of the vertices of a graph G.If G has a proper coloring π such that π(v)∈ L(v)for each vertex v,then we say that G is L-colorable.The graph G is k-choosable if it is L-colorable for every list assignment L satisfying that |L(v)|≥ k for all vertices v∈ V(G).The list chromatic number of G,denoted by xi(G),is the smallest integer k such that G is k-choosable.The concept of list coloring was independently introduced by Vizing and by Erdos,Rubin and Taylor.In 1994,Thomassen proved that every planar graph is 5-choosable,whereas Voigt presented an example of a planar graph which is not 4-choosable in 1993.In 1996,Gutner showed that determining whether a planar graph is 4-choosable is NP-hard.The vertex arboricity,denoted by a(G),of a graph G is the minimum number of subsets into which V(G)can be partitioned so that each subset induces a forest.Similarly,we can define the list vertex-arboricity al(G)of the graph G.It is known that al(G)≤[(Δ+1)/2]for any graph G with maximum degree Δ,and al(G)≤3 for a planar graph G.In this Ph.D.dissertation,we will focus on the list coloring and list vertex-arboricity of planar graphs.The dissertation consists of three chapters.In Chapter 1,we introduce some definitions and notations,give a survey about the research progress of related subjects,and state main results obtained in the dissertation.In Chapter 2,we investigate the list coloring of planar graphs by establishing two sufficient conditions for a planar graph to be 4-choosable.We prove that(1)every planar graph with diameter at most two is 4-choosable;(2)every planar graph with neither 8 cycles nor adjacent 3 cycles is 4-choosable.In Chapter 3,we consider the list vertex-arboricity of planar graphs and show that if a planar graph G satisfies one of the following conditions,then al(G)≤2:(1)without 7 cycles;(2)without choral 6 cycles;(3)without 5 cycles intersecting with 6 cycles;(4)diameter at most two.