Vertex Coloring Of Graphs With Disabled Structure

A coloring ψ:V(G)→{1,2,…,k} of G is 2-distance if any two vertices’ distance at most two from each other get different colors.The minimum number of colors in 2-distance coloring of G is its 2-distance chromatic number,denoted byχ2(G).If each vertex v∈V(G)has a set L(v)of admissible colors,then we say V(G)has a list L.A graph G is said to be 2-distance k-choosable if any list L of size k allows a 2-distance coloring φ such that φ(v)∈(v)whenever v∈V(G).The least k for which G is 2-distance k-choosable is the list 2-distance choice number of G.denoted by χ2l(G).As early as 1977,Wegner[17]proposed the famous conjecture of 2-distance coloring of planar graphs:for a planar graph G,χ2(G)≤7 ifΔ(G)=3,χ2(G)≤Δ(G)+5 if 4≤Δ(G)≤7,χ2(G)≤[3/2Δ(G)]+1 if Δ(G)≥8.This conjecture has not been completely solved.So far,many scholars have devoted themselves to the study of the upper bound of the 2-distance chromatic number of planar graphs.A k-L(2,l)-labelling of G is a function η:V(G)→{0,1,2,…,k} such that|η(x)-η(y)|≥2,if x is adjacent to y and |η(x)-η(y)|≥1,if x and y have a common neighbor.The least k denoted by λ2,1(G)is the L(2,1)-labelling number.If each vertex v∈V(G)has a set L(v)of admissible colors,then we say V(G)has a list L.A graph G is said to be L(2,1)-2-distance k-choosable if any list L of size k allows a k-L(2,1)-labelling φ such that φ(v)∈L(v)whenever v∈V(G).The least k for which G is L(2,1)-2-distance k-choosable is the list L(2,1)-2-distance choice number of G,denoted by λ2,1l(G).The L(2,1)-labelling problem was first proposed by Griggs and Yeh[13],they conjectured that for any graph G,λ2,1(G)≤Δ2 ifΔ(G)>2.Two cycles are said to intersect when they have at least one common vertex.In this paper,we have the following results:Theorem 1.2 For every planar graph with neither 3-cycles nor intersect 4-cycles and Δ(G)≥18,χ2l(G)≤Δ(G)+8.Theorem 1.3 For every planar graph with neither 3-cycles nor intersect 4-cycles and Δ(G)≥28,λ2,1 l(G)≤Δ(G)+12.Theorem 1.4 For every planar graph with maximum degree Δ(G)≤4 and g(G)≥6,χ2l(G)≤10.Theorem 1.5 For every planar graph with maximum degree Δ(G)≤4 and g(G)≥10,χ2l(G)≤7.