?-choosability And Double Cones Over Graphs

This paper is divided into two parts.In the first part,we study the A-list coloring of graphs.A-list coloring is a refined list coloring,which puts the k-colorability and k-choosability of graphs into an unified framework.A-list coloring is defined as follows:For a multi-set ?{k1,k2,…,kq} of positive integers,let k?=?i=1qki.A A-list assignment of G is a list assignment L for which the colour set uv?V(G)L(v)can be partitioned into the disjoint union C1?C2 ?…?Cq of q sets so that for each i and each vertex v of G,|L(v)?Ci|?ki.We say that G is A-choosable if G is L-colourable for any A-list assignment L of G.We say A is trivial if A consists of k?copies of 1,otherwise,it is non-trivial.If A is trivial,then A-choosability is equivalent to k?-colorability.And if ?={k},then A-choosability is equivalent to k-choosability.The partition of k?between {k?} and {1,1,…,1} distinguishes the choosability of graphs in more detail.An important problem of list coloring is which graphs G satisflying ch(G)=?(G).One of the famous problems is Ohba Conjecture.Let ?(k)be the minimum number of vertices in a non-k-choosable k-chromatic graph.Ohba Conjecture means that?(k)?2k+2.And this result has been proved by Noel,Reed,Wu.Let ?(?)be the minimum number of vertices in a non-A-choosable k?-chromatic graph.Let m?(1)be the multiplicity of 1 in A,and let m?(odd)be the number of elements in A that are odd integers.We prove that for any non-trivial A,2k?+1?+ 2??(?)?min{2k?+m?(odd)+2,2k?+5m?(1)+3We then introduce the concept of ?-paintability of graphs,which is an online version of A-choosability.Let ?(?)be the minimum number of vertices in a non-?-paintable k?-chromatic graph.We determine the value of ?(?)when each integer in A is at most 2.In the second part,we study the fractional chromatic number of double cones over graphs.Double cones over graphs is a generalization of Mycielski construction and cones over graphs.We give the formula of fractional chromatic number of ?n,n(G)(n ?2).The definition of double cones over graphs is as follows:Assume that n? m are positive integers and G is a graph.Let Pn,m be the graph obtained from the path with vertices {-m,-(m-1),…0,…,n} by adding a loop at vertex 0.The double cone ?n,m(G)over a graph G is obtained from the direct product G × Pn,m by identiflying V(G)× {n} into a single vertex(,n),identiflying V(G)× {-m}into a single vertex(,-m),and adding an edge connecting(,-m)and(,n).The resulting graph is called double cones over G and denoted as ?n,m(G).By using cones over graphs and double cones over graphs,we construct a graph with vertex number of 187 and fractional chromatic number?3.05 without 3-cycles and 5-cycles.Such graph can be used to construct counterexamples of Hedetniemi Conjecture.