List Total Colorings And 3-Colorings Of Planar Graphs

Let G= (V, E) be a graph with the set of vertices V and the set of edges E, we denote its face set, maximum degree and minimum degree by 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 k-totally-colorable. A total-list-assignment L of G is a set of lists of colors which assign each elements x∈V U E, of G is a list of colors L(x). If G has a proper total-coloringφsuch thatφ(x)∈L(x) for every x∈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∪E, then we say that G is k-list-totally-colorable, or k-totally-choosable. A mappingφ:V�'{1,…, k} is called a k-coloring of G ifφ(u)≠(v) whenever uv∈E. If G admits a k-coloring, then G is said to be k-colorable.About list total colorings 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).Conjecture was posed independently by Vizing and Borodin et al. Steinberg conjectured every planar graph without 4-and 5-cycles is 3-colorable. People have done a serial of research round these two problems.Based on the previous work, this thesis studies 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 withΔ≥8 and without intersecting triangles then χl″＝Δ＋1;(2) If G is a planar graph withΔ≥9 and without adjacent triangles thenχl″=Δ+1;For 3-colorings problems of planar graphs, this paper studies it by using extend-ability lemmas, discharging and identification. The main results obtained as follows:(3) Planar graph without lengths from 4 to 9-cycles with chords is 3-colorable.