The Decomposability And Total Weight Choosability Of Graphs

The coloring of graphs has always been one of the important research topics in the field of graph theory.The concept of classical coloring of graphs has been extended to many aspects.List coloring,online list coloring,DP-coloring and the Alon-Tarsi number of graphs are important research topics in the field of graph coloring.In this thesis,we study the defective coloring and total weight choosability of graphs.Defective list coloring of planar graphs has been studied in a few papers.Cushing and Kierstead proved that every planar graph is 1-defective 4-choosable.As we know,both the Alon-Tarsi number and the DP-coloring number of a graph are upper bounds of the choice number of a graph.Zhu proved a stronger result that every planar graph G has a matching M such that the Alon-Tarsi number of G-M is 4.However,it remains open problems as whether every planar graph G is 1-defective DP-4-colorable and whether there is a matching M such that G-M is DP-4-colorable.Another natural question one may ask is:which planar graph G has a matching M such that the Alon-Tarsi number of G-M is 3?Which planar graph G has a matching M such that G-M is DP-3-colorable?Given two non-negative integers d,h and a graph G,a(d,h)-decomposition of G is a pair(D,H)such that H is a subgraph of G of maximum degree at most h and D is an acyclic orientation of G-E(H)of maximum out-degree at most d.We say G is(d,h)decomposable if G has a(d,h)-decomposition.A graph having an acyclic orientation with maximum out-degree at most d is d-degenerate.It is well-known and easy to see that d-degenerate graphs have choice number,paint number,Alon-Tarsi number and DPchromatic number at most d+1.It follows that if G is(d,h)-decomposable,then G is h-defective DP-(d+1)-colorable.And let H be a subgraph of G of maximum degree at most h,then G-E(H)is DP-(d+1)-colorable and the Alon-Tarsi number of G-E(H)is d+1.In particular,the subgraph H is a matching of G when h=1.This thesis studies decomposability of planar graphs,and proves the following results:(1)Every planar graph G without cycles of lengths 4 and l is(2,1)-decomposable,where l∈{5,6,7,8,9}.(2)Every planar graph G without cycles of lengths 4 and intersecting triangles is(2,1)decomposable.We also study the decomposability of toroidal graphs,and prove the following results:(1)Every toroidal graph G without adjacent triangles is(3,1)-decomposable.(2)Every toroidal graph G without cycles of lengths 3 and j is(2,1)-decomposable,where l∈{4,6}.(3)Every toroidal graph G without cycles of lengths 4 and j is(2,1)-decomposable,where l∈{6,7}.(4)There exists a toroidal graph G without cycles of lengths 4 and 5 is not(2,1)decomposable.The second part of this thesis studies the total weight choosability of graphs.A total weighting of a graph G is a mapping φ:V∪E→R.A total weighting φ is proper if for any edge {i,j} ∈E,∑e∈E(i)φ(e)+φ(i)≠∑e∈E(j)φ(e)+φ(j).A proper total weighting φwith φ(i)=0 for all vertices i is also called a vertex coloring edge weighting.A vertex coloring edge weighting of G using weights ｛1,2,...,k} is called a vertex coloring kedge weighting.Karonski,Luczak and Thomason conjectured that every graph with no isolated edges has a vertex coloring 3-edge weighting.This conjecture is known as the 1-2-3 conjecture and received considerable attention.The list version of edge weighting of graphs was introduced by Bartnicki,Grytczuk and Niwczyk.They conjectured that every graph with no isolated edges is edge weight 3-choosable.The list version of total weighting of graphs was introduced independently by Przybylo and Wozniak and by Wong and Zhu.A graph G is total weight(k,k’)-choosable if for any total list assignment L which assigns to each vertex v a set L(v)of k real numbers,and each edge e a set L(e)of k’ real numbers,there is a proper total L-weighting,i.e.,a mapping f:V(G)∪ E(G)→R such that for each z∈ V(G)∪ E(G),f(z)∈ L(z),and for each edge uv of G,∑e∈E(u)f(e)+f(u)≠∑e∈E(v)f(e)+f(v).Wong and Zhu conjectured that(1)every graph with no isolated edges is total weight(1,3)-choosable,and(2)every graph is total weight(2,2)-choosable.Recently,Cao proved that every graph with no isolated edges is total weight(1,17)-choosable.This result was improved by Zhu.It was shown that every graph with no isolated edges is total weight(1,5)-choosable.In this thesis,we study the total weight(1,3)-choosability of some special graph classes,and prove the following results:(1)If G decomposes into complete graphs of odd order,then G is total weight(1,3)choosable.(2)Every Eulerian graph G of large order and with minimum degree at least 0.91|V(G)|is total weight(1,3)-choosable.(3)Every graph G with minimum degree at least 0.999|V(G)| is total weight(1,4)choosable.