Three-List-Colorable And FM Decomposition Of Plane Graphs

A k-coloring of G is a mappingφ:V→{1,…,k} such thatφ(u)≠φ(v) whenever uv∈E.G is said to be k-colorable if G admits a k-coloring.Let G=(V, E). A list-assignment of a graph G is a collection of lists of available colors which assign each vertex v∈V(G) a list of available colors L(v). If G has a proper coloring such that the coloring from L(v) for every vertex v, then we say that G is L-colorable. We say that G is k-list-colorable, if it is L-colorable for every list-assignment L with |L(v)|≥k for all v∈V, where k is a positive integer.In 1996, Gutner proved that it is NP-hard to prove the problems that a given plane graph is 3-list-colorable or 4-list-colorable. Thus it is significant for us to study suffi-cient conditions for plane graphs to be 3-list-colorable or 4-list-colorable.In 2006, Montassier et al. proved that a plane graph is 3-list-colorable if it contains neither 4-,5-,6-cycles nor two triangles at distance less than 3; In 2008, Montassier et al. proved that a plane graph is 3-list-colorable if it contains two 6--cycles at distance not less than 3. Following previous works, by discharging and analyzing structure properties, in this dissertation, we get a better result:(1) Every plane graph is 3-list-colorable if it contains neither triangles and 5--cycles at distance less than 3 nor intersecting i-cycles and j-cycles where 4≤i≤j≤6;In 2005, Lam et al. proved that a plane graph without 3-,5-, and 6-cycles is 3-list-colorable; In 2008, zhang et al. proved that a plane graph without 5-,6-,7- cycles, and without two triangles at distance less than 3, and a plane graph without 5-, 6-,8-cycles, and without two triangles at distance less than 2 are 3-list-colorable; In 2008, Montassier et al. proved that a plane graph is 3-list-colorable if it contains two 7--cycles at distance not less than 2. Following previous works, by discharging and analyzing structure properties, in this dissertation, we get a better result:(2) Every plane graph is 3-list-colorable if it contains neither two triangles at distance less than 2 nor two adjacent cycles with total length less than 11;In 1995, Thomassen proved that a plane graph with girth 5 is 3-list-colorable; In 2009, Li proved that a triangle-free plane graph is 3-list-colorable if every 4-cycle in it is not intersecting to any 4-or 5-cycles. Following previous works, by colors extending and inducting, in this dissertation, we get a better result:(3) Every triangle-free plane graph is 3-list-colorable if every 4-cycle in it is not adjacent to any 4-or 5-cycles.By a decomposition of graph G we mean that G is decomposed into several sub-graphs, and each edge appears only once in subgraphs. By an FM-coloring of a graph we mean a partition of its edges into a forest and a matching.In 2002, He et al. proved that a planar graph with girth at least 11 can be decom-posed into a forest and a matching; In 2004, Kleitman et al. proved the same statement for planar graphs with girth at least 10; In 2008, Borodin et al. proved the same state-ment for planar graphs with girth at least 9, what's more, they said that whether a planar graph with girth at least 8 can be decomposed into a forest and a matching remains open and is an interesting. By identifying vertices and discharging, we proved that:(4) Every planar graph with girth at least 8 can be decomposed into a forest and a matching.