The K-L(P,1)-choosability Of Planar Graphs

Let N be the set of positive integers and we assign each vertex v of G a list L(v)which L(v)? 2N.If a graph G has a mapping ?:?(v)? L(v)which |L(v)|?k for every v ?V(G)such that |?(u)-?(v)|? p when d(u,v)=1,and |?(u)-?(v)|?1 when d(u,v)=2 for any two vertices u and v,then we say the graph G is k-L(p,1)-choosable.The least k such that G is k-L(p,1)-choosable is called the k-L(p,1)-choice number of G and is denoted by ?p,1l(G).A graph G has a coloring ?:V(G)?{1,2,...,k} such that |?(u)-?(v)|?1 when d(u,v)?2 for any two vertices u and v,then we say the graph G has a 2-distance coloring.The minimum k such that.G has a 2-distance coloring is its 2-distance chromatic number,denoted by ?2(G).For k-L(p,1)-choosable graphs,when p=1,the problem of k-L(1,1)-choosability for graphs is more difficult than the problem of 2-distance coloring for graphs.Because the list of 2-distance coloring for every vertex is {1,2,...,k} and the list of k-L(1,1)-choosability is arbitrary |L(v)|?k,?2(G)??1,1l(G).In 1977,Wegner proposed a very important conjecture about the 2-distance coloring of planar graphs:For a planar graph G,(1)?2(G)? 7 if ?(G)=3;(2)X2(G)??(G)+5 if 4 ??(G)? 7;(3)?2(G)?[3/2?(G)]+1 if ?(G)? 8.The conjecture is still open.A graph G has a mapping ?:V(G)?{0,1,2,...,k} such that |?(u)-?(v)|? 2 when d(u?v)=1,and |?(u)-?(v)|? 1 when d(u,v)=2 for any two vertices u and v,then we say the graph G has an L(2,1)-labeling.The least k such that G has an L(2,1)-labeling is called the L(2,1)-labeling number of G and is denoted by ?2,1(G).For k-L(p,1)-choosable graphs,when p=2,the problem of k-L(2,1)-choosability for graphs is more difficult than the problem of L(2,1)-labeling for graphs.Because the list of L(2,1)-labeling number for every vertex is {0,1,2,…,k} and the list of k-L(2,1)-choosability is arbitrary |L(v)|?k,?2,1(G)+1??2,1(G).This paper consists of four chapters:In Chapter 1,we mainly introduce the k-L(p,1)-choosability of planar graphs,give some definitions and symbols uesed in this paper,and list our main resultsIn Chapter 2,we extend the result of Bu Yuchua and Shang Chunhui[List 2-distance coloring of planar graphs without short cycles,2016]:each planar graph G with g(G)>5 and ?(G)? 12 is(?+6)-L(1,1)-choosable.We prove that each planar graph G with g(G)? 5 and ?(G)? 30 is(?+5)-L(1,1)-choosable.In Chapter 3,we improve the result of Bu Yuehua and Yan Xiaoyan[List 2-distance coloring of planar graphs,2015]:each planar graph G with g(G)? 5 and ?(G)?5 is 13-L(1,1)-choosable.We prove that each planar graph G with g(G)?5 and ?(G)? 5 is 12-L(1,1)-choosableIn Chapter 4,we prove that each planar graph G with g(G)? 6 and ?(G)? 15 is(?+6)-L(2,1)-choosable.