Multiple Coloring And Edge Weighting Of Planar Graphs

This thesis studies two kinds of colorings for planar graphs:multiple list colouring of planar graphs and edge weighting vertex coloring of planar graphs.Assume G is a graph and b is an integer.A 6-fold coloring of G is a mapping? which assigns to each vertex v of G a set ?(v)of b colors so that for any two adjacent vertices u and v,?(u)??(v)=(?).say G is(a,b)-choosable if for any a-list assignment L of G,there exists a b-fold coloring ? of G for which ?(v)(?)L(v)for each vertex v.We say G is strongly fractional r-choosable if for any positive integer m,G is([rml,m)-choosable.The strong fractional choice number of G is defined as chf*(G)=inf{r:G is strongly fractional r-choosable}.For a family g of graphs,let chf*(g)=sup{chf*(G):G ?g}.Recently,Zhu[28]proved that for any integer m,there is a planar graph G which is not(4m+[3m-1/9],m)-choosable;and Jiang and Zhu[11]proved that for any integer m,there is a triangle free planar graph G which is not(3m+[m/17]-1,m)-choosable.Let P denote the family of planar graphs and for a positive integer k,let Pk denote the family of planar graphs with no cycles of length k.So chf*(P)?4+2/9 and chf*(P3)?3+1/17.In this thesis,we study the strong fractional choice number of planar graphs without 4-cycles and planar graphs without 5-cycles.We prove that for any integer m,there is a C4-free planar graph G which is not(3m+[m/2]-1,m)We-choosable,and for any integer m,there is a C5-free planar graph G which is not(3m+[m/4]-1,m)-choosable.As a consequence,we have chf*(P4)? 3+1/2 and chf*(P5)?3+1/4.Edge weighting of graphs was introduced by Karonski,Luczak and Thomason[14]in 2004.Given an integer k,a k-edge weighting vertex coloring of a graph G is a mapping w:E(G)?{1,2,...,k} so that for any two adjacent vertices u and v,?e?E(u)w(e)??e?E(v))w(e).Karonski,Luczak and Thomason[14]conjectured that every graph G with no isolated edges has a 3-edge weighting vertex coloring and proved that the conjecture for 3-colorable graphs.In 2010,Kalkowski,Karonski and Pfender[13]proved that every graph with no isolated edges has a 5-edge weighting vertex coloring,and in 2017,Wu,Zhang and Zhu[27]proved that 4-colorable 4-edge con-nected graphs have 3-edge weighting vertex coloring.Recently,Lyngsie,Thomassen and Zhong 17]proposed a conjecture that strengthens the four color theorem.We de-fine a k-edge weighting n-coloring of a graph G as a mapping w:E(G)?{1,2,...,k}so that for any two adjacent vertices u and v,?e?E(u)w(e)??e?E(v)w(e)(mod n).Lyngsie,Thomassen and Zhong conjecture that every planar graph with no isolated edge has a 3-edge weighting 4-coloring.This conjecture is considerably-stronger than the four color theorem.Using the four color theorem,they proved that every plane triangulation has a 3-edge weighting 4-coloring and that every 4-colorable 4-edge con-nected graph has a 3-edge weighting 4-coloring.In this paper,we prove that Lyngsie,Thomassen and Zhong conjecture holds for trees.By using the four color theorem,we prove that every planar graph has a 4-edge weighting 4-coloring,and every 4m-colorable graph with no isolated edge has a 4m-edge weighting 4m-coloring.