Total Colorings And List Total Colorings Of Planar Graphs

Given a plane graph G=(V, E), we denote its vertex set, edge set, face set, maximum degree and minimum degree by V, E, F, Δ and δ, respectively. If one can use k colors to color all elements in V U E such that any two adjacent or incident elements receive distinct colors, then G is said to be normal κ-totally-coloring, and also called κ-totally-colorable. The total chromatic number of G is the minimum positive integer κ so that G has a κ-totally-coloring.,Obviously, the total chromatic number is at least Δ+1. A total-list-assignment L of G is a set of lists of colors which assign each elements x∈V∪E, of G is a list of colors L(x). If G has a proper total-coloring φ such that φ(x)∈L(x) for every∈e V U E, then G is said to be L colorable. If G is L-colorable for every total-list-assignment L with|L(x)|=k for every x∈V U E, then we say that G is κ-list-totally-colorable, or κ-totally-choosable.As early as1960s, Vizing and Behzad independently conjectured that for any sim-ple graph G, it had a (Δ+2)-totally-coloring. So far, the only problem has not yet been solved if the plane graphs with Δ=are8-totally-colorable. About list total col-orings and list edge colorings of graphs, we have following conjectures (List Coloring Conjecture):For any graph G,(a)χl’(G)=χ’(G);(b)χl"(G)=χ"(G).Based on the previous work, this thesis studies the total colorings and the list-total-colorings problems of planar graphs. The main results obtained in this dissertation may be summarized as follows:(1) If G is a planar graph without3-cycles adjacent to6-cycles, then χ"=Δ+2; (2) If G is a planar graph with△≥7and without adjacent4-cycles,then χl"=△+1；If G is a planar graph with△≥8and without3=cycles adjacent to5=cycles,then χl"=△+1；If G is a planar graph with△≥6and without3-cycles adjacent to5-cycles,then χ"=△+2；(3) If G is a planar graph with△≥9and without adjacent4-cycles,then χ"=△+1.