Research On The Problem Of (2,1)-total Choosability Of Graphs

Let k,p∈Z+.A graph G is said to be k-(p,1)-total labelable if and only if there is a function η from V(G)∪ E(G)to {0,1,2,…,k} so that(1)|η(u)-η(v)|≥1 if uv∈E(G);(2)|η(e1)-η(e2)|≥1 if the edges e1 and e2 are adjacent;(3)|η(u)—η(e)|≥p if the vertex u is incident to the edge e.Then,77 is called a(p,1)-total labeling mapping of graph G.This paper mainly focuses on the list version of(p,1)-total labeling problem of graphs.Suppose that a list assignment of a graph G is a function L:V(G)∪ E(G)→ 2N.If there exists a(p.1)-total labeling η that η(x)∈ L(x)for all x ∈ V(G)∪ E(G),then we say G is L-(p,1)-total labelable.Then,η is called an L-(p,1)-total labeling mapping of graph G.Suppose L is a list assignment of G such that |L(x)|=k for all x ∈ V(G)∪ E(G).If G has an L-(p,1)-total labeling function η for any such L,then the graph G is k-(p,1)-total choosable.The(p,1)total choice number of G,denoted by Cp,1T(G),is the minimum k such that G is k-(p,1)-total choosable.In particular,when p=2,C2,1T(G)is the(2,1)-total choice number of G.On the(p,1)-total choosable problem of graphs,Yong Yu proposed a weak list(p,l)-total labeling conjecture and guessed that the upper bound of(p,1)-total choice number is Δ+2p.Yong Yu proved that the weak list(p,1)-total labeling conjecture holds for paths,trees and stars.And for the outer planar graph and graph embedded in surface with Euler characteristic ε,the weak list(p,1)-total labeling conjecture is true under the condition of maximum degree.In this paper,we mainly study the(2,1)-total choosable problem of planar graphs and 1-planar graphs,and partially answer the weak list(p,1)-total labeling conjecture.In Chapter 1,we first introduce the basic terms involved in this paper,and give the definitions,research history and current situation of total coloring and[r,s,t]coloring of graphs.Then,we introduce the definition,background and research status of(2,1)-total labeling and its list version of graphs,and show the relationship between(2,1)-total labeling of graphs and total coloring or[r,s,t]-coloring of graphs.Finally,the main conclusions of this paper are described.In Chapter 2,we study the(2,1)-total choice number of planar graphs,and prove three conclusions by using the discharging method.(1)If G is a planar graph with Δ(G)≥7 and 3-cycle is not adjacent to k-cycle,k ∈ {3,4},then C2,1T(G)≤Δ+4.(2)If G is a planar graph with Δ(G)≥ 8 and i-cycle is not adjacent to j-cycle,where i,j∈{3,4,5},then C2,1T(G)≤ Δ+ 3.(3)If G is a planar graph with Δ(G)≥ 11,then C2,1T(G)≤Δ+4.We prove that the weak list(p,1)-total labeling conjecture holds for planar graphs with Δ(G)≥11 when p=2.In Chapter 3,we study the(2,1)-total choice number of 1-plane graphs.Firstly,we introduce some important lemmas on the properties of 1-plane graphs,and then prove the theorem by using the associated plane graph and discharging method:If G is a 1-planar graph with Δ(G)≥12 and contains no adjacent 3-cycle or adjacent 4-cycle,then C2,1T(G)≤ Δ+4.In Chapter 4,we give the problems for further research.