The Strong Fractional Choice Number And The Strong Fractional Paint Number Of Graphs

Assume G is a graph and r is a real number.We say G is strongly fractional r-choosable(resp.,strongly fractional r-paintable)if G is(a,b)-choosable(resp.,(a,b)-paintable)for any(a,b)for which a/b? r.The strong fractional choice number of G is de-fined as ch_f^s(G)=inf{r?R:G is strongly fractional r-choosable}.The strong fractional paint number of G is defined as ?_f,p^s(G)=inf{r ?R:G is strongly fractional r-paintable}.This thesis studies the concepts of the strong fractional choice number ch_f^s(G)and the strong fractional paint number ?_f,p^s(G)of a graph G.First,we prove that for any finite graph G,ch_f^s(G)and ?_f,p^s(G)are rational num-bers,and that for any positive integers p,q where p? 2q satisfying 2p/2q+1?[p/q],there exists a graph G with ch_f^s(G)=?_f,P^s(G)=p/q.Second,we study the upper bound of these parameters for some classes of graphs and prove the following results:1.For complete bipartite graphs.We apply the technique of 2-coloring of hyper-graph and show that complete bipartite graph G with n vertices has ch_f^s(G)?1+[log₂n].2.For complete multipartite graphs.Given a graph G which is(km,m)-paintable for any positive integer m.If |V(G)|?k+k/t-1,then G(?)Kt is((k+1)m,m)-paintable for any positive integer m.As a result,we show that ch_f^s(K_2*k)=?_f,P^s(K_2*k)=k.3.For minor-closed graphs.We prove that for every graph H,?>0,there is an integer g such that for any G does not contain H as a minor and of girth at least g,ch_f^s(G)?2+?.Consequently,we show that every planar graph of girth at least g(g?6)has strong fractional choice number at most 2+1/[(g+6)12].4.For 3-paint-critical graphs,which are not 3-paintable but any proper subgraph of which is 2-paintable.We show that for each graph in this family,if it is an odd cycle,say of length 2k+1,then ?_f,P^s(G)=2+1/k.Otherwise,ch_f^s(G)??_f,P^s(G)?The strong fractional choice number of a family g of graphs is the supremum of the strong fractional choice number of graphs in g.Let P denote the class of planar graphs and P_k1,..,kq denote the class of planar graphs without k?_f,P^s_i-cycles for i=1,..,q.We prove that 3+1/2?ch_f^s(P₄)?4,ch_f^s(P_k)=4 for k?{5,6},3+1/12?ch_f^s(P_4,5)?4 and ch_f^s(P)? 4+1/3.The last result improves the lower bound 4+2/9 in[X.Zhu.Multiple list colouring of planar graphs.J.Combin.Theory Ser.B,122:794-799,2017].We then study the strong fractional choice number of 3-choice-critical graphs.Such graphs are characterized by Voigt in 1998,which includes:(1)An odd cycle.(2)Two vertex-disjoint even cycles joined by a path(possibly a vertex).(3)?_r,s,t with r? 1,s,t?3,and r,s,t having the same parity.(4)?_2,2,2,2p graph with p?1.From a result proved by Tuza and Voigt in 1996 that ?_2,2,2,2 is(4m,2m)-chosable for any posi-tive integer m,Voigt conjectured that every bipartite 3-choice-critical graph is(2m,m)-choosable for any even integer m.If this conjecture is true,then the strong fractional choice number of every bipartite 3-choice-critical graph is 2.However,the conjecture was refuted by Meng,Puleo and Zhu in 2017.They showed that if G=?_r,s,t where r,s,t have the same parity and min{r,s,t}? 3,or G=?_2,2,2,2p with p? 2,then G is not(4,2)-choosable.On the other hand,all the other bipartite 3-choice critical graphs are(4,2)-choosable.We strengthen the result of Meng,Puleo and Zhu and show that all such(4,2)-choosable bipartite 3-choice-critical graphs are also(4m,2m)-choosable for every positive integer m.On the other hand,for those non-(4,2)-choosable bipartite 3-choice-critical graphs,we show that they are all(2m+1,m)-choosable for each positive integer m.As a result,the strong fractional choice number of every graph in this fam-ily is determined:If G is an odd cycle of length 2k+1,then ch_f^s(G)=?_f,P^s(G)=2+1/k.Otherwise,ch_f^s(G)=2.