Total Coloring,List Coloring And Acyclic Total Coloring Of Planar Graphs

All graphs considered in this paper are simple, finite and undirected. Let G be a graph. We use V(G), E(G),△(G), δ(G) and g to denote the vertex set, the edge set, the maximum degree the minimum degree and the girth of G, respectively. For a vertex v∈V, let N(v) denote the set of vertices adjacent to v, and let d(v)=|N{v)|denote the degree of v. A k-cycle is a cycle of length k,a3-cycle is usually called a triangle, and a short cycle is a cycle of length at most5.A total-k-coloring of a graph G is a coloring of V U E using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number X"(G) of G is the smallest integer k such that G has a total-k-coloring. The chromatic number X(G) of G and the edge chromatic number (or chromatic index) X’(G) of G are defined similarly in terms of coloring vertices alone or edges alone, respectively. Clearly, X"(G)≥△+1. Behzad and Vizing posed independently the following famous conjecture.Conjecture1. For any graph G, X"(G)≤△+2. This conjecture was confirmed for a general graph with△≤5. But for planar graph, the only open case is△=6.we adopt the "discharging" method,We give the exact value of total chromatic number of planar graphs with restrictions.Firstly, we investigate the total chromatic number of planar graphs with-out intersecting short-cycles, and get the following results: Theorem1Let G be a planar graph with△≥7.If G contains no intersecting triangles,then X"(G)=△+1.Theorem2Let G be a planar graph with△≥7.If no3-cycle has a common vertex with a4-cycle,then x"(G)=△+1.Theorem3Let G be a planar graph with△≥7.If G contains no intersecting5-cycles,then X"(G)=△+1.Secondly,we study the total chromatic number of planar graphs without chordal6-cycles,and get the following result:Theorem4Let G be a planar graph with△≥=7.If G cont ains no chordal6-cycles,then X"(G)=△+1.Thirdly,we consider the total chromatic number of planar graphs with small maximum degree,and get the following result:Theorem5Let G be a planar graph of maximum degree△and girth g,and there is an integer t(>g)such that G has no cycles of length from g+1to t.Then the total chromatic number of G is△+1if(△,g,t)∈{(5,4,6),(4,4,11)).Theorem6Let G be a planar graph of maximum degree△≥3and girth g,each vertex is incident with at most one g-cycle and there is an integer t(>g)such that G has no cycles of length from g+1to t.Then X"(G)=△+1if one of the following conditions holds.(α)g=5and t≥29,(b)g=6and t≥17,(c)g=7and t≥13；(d)g=8and t≥11,(e)g=9and t≥10,(f)g≥10.Finally,we study the total chromatic number of planar graphs from the view of degree sum of a triangle,and get the following results:Theorem7Let G be a planar graph with△≥7. If s△≥18and δ△≥6,then X"(G)=△+1.where s△=min{d(u)+d(u)+d(w)|uvw is a triangle of G}and δ△=min{d(u),d(v),d(w)|uvw is a triangle of G}. Theorem8Let G be a planar graph with△>8. If s△>19and δ△≥5, then X"{G)=△+1.Another topic discussed in this thesis is list coloring. We say that a mapping L is an edge assignment for the graph G if it assigns a list L(e) of possible colors to each edge e∈E(G). If G has a proper edge-coloring φ such that φ(e)∈L(e) for every edge e∈E(G), then we say that G is edge-L-colorable or φ is an edge-L-coloring of G. The graph G is edge-k-choosable if it is edge-L-colorable for every edge assignment L satisfying|L(e)|≥k for each edge e∈E(G). The list edge chromatic number of G, denoted by x’i(G), is the smallest integer k such that G is edge-k-choosable. The list chromatic number Xi(G) and the list total chromatic number X"i(G) of G can be defined similarly in terms of coloring vertices alone, or both vertices and edges, respectively. It follows directly from the definition that X’i(G)> X’(G)≥△and X"i(G)≥X"(G)≥△+1. We mainly discussed list colorings on planar graphs in this thesis, get the following results:Theorem9Let G be a planar graph with△≥8. If G contains no3-cycle is adjacent to k-cycles for some k∈{4,5}, then X’i{G)=△and X"i(G)=△+1.The last topic discussed in this thesis is acyclic total coloring. An acyclic total coloring is a proper total coloring of a graph G such that there are at least4colors on those vertices and edges incident with a cycle of G. The acyclic total chromatic number of G, X"α(G), is the smallest integer k such that G has an acyclic total coloring. The acyclic total coloring was introduced by Sun and Wu, and they give a conjecture on acyclic total coloring.Conjecture2.△(G)+1≤X"α(G)≤△(G)+2for any graph G.we study an upper bound of acyclic total chromatic number of planar graphs, and get the following results: Theorem10Let G be a planar graph with△≥6.If no3-cycle has a common vertex with a4-cycle,then X"α:(G)≤△+2.Theorem11Let G be a planar graph with△≥7.If G contains no intersecting triangles,then X"α:(G)≤△+2.Theorem12Let G be a planar graph with△≥=7.If a short i-cycle is not adjacent to a short j-cycle(i≠j),then X"∝(G)≤△+2.Theorem13Let G be a planar graph with△≥9.Then X"α(:(G)≤△+2.