| 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. |
