Total Coloring Of Plane Graphs

For a plane graph G,we denote its vertex set,edge set,face set,maximum degree and minimum degree by V,E,F,Δandδ,respectively.If one can useκcolors to color all elements in V∪E such that any two adjacent or incident elements receive distinct colors,then G is said to beκ-totally-colorable.The total chromatic number of G is defined as:_χT(G) = min{κ∣G isκ-totally-colorable}.Obviously,at leastΔ+ 1 colors are needed to color G totally,that is,_χT(G)≥Δ+ 1.As early as 1960s,Vizing and Behzad independently conjectured that for every graph G,_χT(G)≤Δ+ 2.This conjecture was known as Total Coloring Conjecture, in short,TCC.TCC is extensively researched in the literature.It is interesting to notice that many plane graphs are proved to be(Δ+ 1)-totally-colorable,i.e.,the exact result has been obtained.Up to date,plane graphs G withΔ≥9 have been proved that _χT(G) =Δ+ 1.However,for plane graphs G with 4≤Δ≤8,no one has found the counterexamples that are not(Δ+ 1)-totally-colorable.So,we conjecture that plane graphs G withΔ≥4 are(Δ+ 1)-totally-colorable.As we know,TCC is conjectured for every graph G and here the conjecture focus on plane graph.Thus,we call it Total Coloring COnjecture for Plane Graphs,in.short,PTCC.This dissertation mainly studies PTCC for smaller-maximum degree,say,Δ= 8,7,6.It is proved that(Ⅰ)_χT(G) = 7,if G is a plane graph withΔ= 6 and without 4-cycles;(Ⅱ) _χT(G) = 8,if G is a plane graph withΔ= 7 and without 5-cycles; (Ⅲ) _χT(G) = 9,if G is a plane graph withΔ= 8 and without(ⅰ) 5-cycles with chords;or(ⅱ) 6-cycles with chords;or(ⅲ) intersecting triangles;or(ⅳ)adjacent triangles.