List Vertex (Edge,Total) Coloring And List Linear Arboricity Of Planar Graphs

The study of graph theory started two hundred years ago.The earliest known paper was written by Euler(1736)to solve the Konigsberg seven-bridge prob-lem.Graph coloring has been one of the most important directions of graph theory since the arose of the well-known Four Color Problem.Graph color-ing has real-life applications in optimization,computer science and network design.Here,we study the total coloring,list coloring,neighbor sum distin-guishing total coloring and linear L-choosable arboricity.All graphs in this thesis are simple,undirected and finite graphs.Let G=(V,E)be a graph.For a vertex v ? V(G),let NG(v)be the set of neighbors of v in G and let dG(v)= |NG(v)| be the degree of v in G.The maximum degree and minimum degree of G is denoted by ?(G)and ?(G),respectively.For convenience,throughout this thesis,we set ?=?(G)and? = ?(G).A k-total-colorin.g of a graph G is a coloring of V(G)U E(G)using(1,2,...,k)colors such that no two adjacent or incident elements receive the same color.The total chromatic number X?(G)is the smallest integer k such that G has a k-total-coloring.As early as 1960s,Vizing and Behzad independently conjectured that for any graph G,? ??"(G)? ?+2.This conjecture was known as Total Coloring Conjecture.This conjecture has been confirmed for general graphs with ? ? 5.For planar graphs,the only open case is ? = 6.It is interesting to notice that many planar graphs are proved to be ?"(G)= ? + 1,i.e.,the exact result has been obtained.Up to date,for each planar graph with ? ? 9,?"(G)= ? + 1.However,for planar graphs with 4 ? ? ? 8,no one has found counterexamples that are not(? + 1)-total-colorable.So,Wang Yingqian et al.conjectured that planar graphs with ? ? 4 are(? + 1)-totally-colorable.In chapter 2,we study total coloring of planar graphs and obtain three results:(1)Let G be a planar graph with maximum degree ? ? 8.If every two chordal 6-cycles are not adjacent in G or every 6-cycle contains at most one chord,then ?"(G)—? + 1.(2)Let G be a planar graph G with maximum degree? ? 8.If any 7-cycle of G contains at most two chords,then ?"(G)= ? +1.(3)Let G be a planar graph without intersecting chordal 5-cycles,that is,every vertex is incident with at most one chordal 5-cycle.If ? ? 7,then?"(G)= ? + 1.A mapping L is said to be an assignment for a graph G if it assigns a list L(v)of colors to each vertex v ?V(G).If it is possible to color G so that every vertex gets a color from its list and no two adjacent vertices receive the same color,then we say that G is L-colorable.A graph G is k-choosable if G is an L-colorable for any assignment L of G satisfying |L(v)|?k for every vertex v ?V(G).We prove that if every 5-cycle of G is not simultaneously adjacent to 3-cycles and 4-cycles,then G is 4-choosable.A mapping L is said to be a total assignment for a graph G if it assigns a list L(x)of colors to each element x?(G)? E(G).Given a total assignment L of G,an L-total coloring of G is a proper total coloring such that each element receives a color from its own list.A graph G is k-total-choosable if G has a proper L-total-coloring for every preassigned total assignment L with |L(x)| ? k for every x ? V U E.The list total chromatic number or total choosability of G,denoted ?l"(G),is the smallest integer k such that G is k-total-choosable.The list edge chrormatic number(or edge choosability)?l'(G)are defined similarly in terms of coloring only edges.In chapter 3,if every 5-cycles of G is not adjacent to 4-cycles,we prove that Xl'(G)??,?."(G)= ? + 1if?(G)? 8,and ?l'(G)? ? + 1,?l"(G)? ? + 2 if ?(G)? 6.Recently,magic and antimagic labellings and the irregularity strength and other colorings and labellings related to "sum" of the colors have received much attention.Among them there are the famous 1-2-3 Conjecture and 1-2 Conjecture.In chapter 4,we will give the definition of neighbor sum distinguishing total coloring.We also list the research progress and the corre-sponding conjectures of neighbor sum distinguishing total coloring.Let f(v)denote the sum of the colors of a vertex v and the colors of all incident edges of v.A total k-neighbor sum distinguishing-coloring of G is a total k-coloring of G such that for each edge uv ? E(G),f(u)? f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted by??"(G).Pilsniak and Wozniak conjectured that for any graph G with maxi-mum degree ?(G)holds that ??"(G)? ?(G)+ 3.This conjecture has been proved for complete graphs,cycles,bipartite graphs,subcubic graphs,sparse graphs,series parallel graphs and planar graphs with ?? 14.We prove for a graph G with maximum degree ?(G)which can be embedded in a surface? of Euler characteristic ?(?)?0,then ??"(G)? max{?(G)+ 2,16}.Lastly,we study the linear L-choosable arboricity of graph.A linear forest is a graph in which each component is a path.The linear arboricity la(G)of a graph G as defined by Harary is the minimum number of linear forests in G,whose union is the set of all edges of G.Akiyama et al.posed the following conjecture:For any regular graph G,la(G)?[?(G)+1/2].Clearly,la(G)?r[?(G)/2]So for every regular graph G,we have la(G)? ?[?(G)+1]/2],Hence,the conjecture above is equivalent to the linear arboricity conjecture:For any simple graph G,[?(G)/2]?la(G)?[?(G)+1/2].A list assignment L to the edges of G is the assignment of a set L(e)C N of colors to every edge e of G,where N is the set of positive integers.If G has a coloring?(e)such that v(e)G L(e)for every edge e and(V(G),?-1(i))is a linear forest for any i? C?,where C?= {?(e)|e ? E(G)},then we say that G is linear L-colorable and ? is a linear L-coloring of G.We say that G is linear k-choosable if it is linear L-colorable for every list assignment L satisfying|L(e)| ? k for all edges e.The list linear arboricity lalist(G)of a graph G is the minimum number k for which G is linear k-list colorable.It is obvious that la(G)? lalist(G).In chapter 5,we prove that if G is a planar graph such that every 7-cycle of G contains at most two chords,then G is linear[?+1/2]-choosable if ?(G)? 6,and G is linear[?/2]-choosable if ?(G)>11.Chapter 6 is the conclusion of the thesis.We give some graphs that can be studied in the future and we show some graph coloring problems for future works.