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.