| A graph is planar if it can be embedded into the plane so that its edges meet only at their ends. The distance between two cycles is the minimum distance between every pair of vertices which are from different cycles. A 3-cycle is often called a triangle.Let G = (V, E) be a planar graph. If there is a functionφ: V→{1, 2,…k} such thatφ(u)≠φ{v} whenever (?)uv∈E, then we say thatφis a k-vertex -coloring of G. If G has a k-vertex-coloring, then we say that G is k-colorable. The coloring number X(G) is the minimum integer k for G to be k-colorable. Assign a list of available colors L(v) for each vertex v of G, L = {L(v) | v∈V} is a color list of G. For a color list L of G, if there is a functionφsuch that (1)for (?)v∈V,φ(v)∈L(v), (2) (?)uv∈E, there isφ(u)≠φ(v),then we say G is L-colorable. If G is L-colorable for all color list L which satisfy |L(v)|≥k,((?)v∈(?)), then we say G is k-list-colorable. The list-coloring number ch(G) is the minimum integer k for G to be k-list-colorable.In 1996, Gutner proved that it is NP-hard to decide a given planar graph is 3-list-colorable. Thus it is significant for us to study sufficient conditions for planar graphs to be 3-list-colorable.This dissertation studies 3-list-colorability of planar graphs with sparse triangles, main results obtained are as follows:(1) Every planar graph with neither 4, 6, and 8-cycles nor triangles at distance less than 2 is 3-list-colorable. (2) Every planar graph with neither 4, 7, and 9-cycles nor triangles at distance less than 3 is 3-list-colorable.(3) Every planar graph with neither 4, 8, and 9-cycles nor triangles at distance less than 3 is 3-list-colorable... |
PDF Full Text Request