Every Graph Embedded on the Surface with Euler Characteristic Numberε=-1 is Acyclically 11-choosable

A proper vertex coloring of a graph G is acyclic if there is no bicolored cycles in G.A graph G is acyclically k-choosable if for any list assignment L={L(v):v∈V(G)}with|L(v)|≥k for each vertex v∈V(G),there exists an acyclic proper vertex coloringφof G such thatφ(v)∈L(v)for each vertex v∈V(G).In this paper,we prove that every graph G embedded on the surface with Euler characteristic numberε=-1 is acyclically 11-choosable.

Every Toroidal Graph Is Acyclically 8-Choosable

A proper coloring of a graphG is acyclic if G contains no 2-colored cycle.A graph G is acyclically L-list colorable if for a given list assignment L={L（v）：v∈V（G）},there exists a proper acyclic coloringφof G such thatφ（v）∈L（v）for all v∈V（G）.If G is acyclically L-list colorable for any list assignment L with｜L（v）｜≥k for all v∈V（G）,then G is acyclically k-choosable.In this article,we prove that every toroidal graph is acyclically 8-choosable.

ON 3-CHOOSABIL ITY OF PL ANE GRAPHSON3 -CHOOSABIL ITY OF PL ANE GRAPHS WITHOUT 6-,7-AND 9-CYCLES

The choice number of a graph G,denoted byχl(G) ,is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own listno matter whatthe lists are.In this paper,itis showed thatχl(G)≤ 3 for each plane graph of girth not less than 4 which contains no 6- ,7- and 9- cycles

AN SIRS EPIDEMIC MODEL

This paper considers an SIRS epidemic model that incorporates constant immigrati on rate, a general population size dependent contact rate and proportional tran sfer rate from the infective class to susceptible class.A threshold parameter σ is identified. If σ≤1, the disease free equilibrium is globally stab le. If σ>1, a unique endemic equilibrium is locally asymptotically stable. For two important special cases of mass action incidence and standard incidence, global stability of the endemic equilibrium is proved provided the threshold is larger than unity. Some previous results are extended and improved.

Improper Choosability of Planar Graphs without 6-circuits

A graph G is called（k,d）＊-choosable if for every list assignment L satisfying ｜L（v）｜=k for all v ∈ V（G）,there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself.In this paper,it is shown that every planar graph without 6-circuits and a triangle adjacent to itself or a quadrangle is（3,1）＊-choosable.

Chromatic Choosability of a Class of Complete Multipartite Graphs

A graph G is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph G with 2Х（G） ＋ 1 or fewer vertices is chromatic choosable. It is easy to see that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. But at present only for some special cases of complete multipartite graphs, Ohba＇s conjecture have been verified. In this paper we show that graphs K6,3,2＊（k-6）,1＊4 （k ≥ 6） is chromatic choosable and hence Ohba＇s conjecture is true for the graphs K6,3,2＊（k-6）,1＊4 and all complete k-partite subgraphs of them.

(4m, m)-CHOOSABILITY OF PLANE GRAPHS

A graph G is (a, b)-choosable for nonnegative integers a > b if for any given family {A(v)\v ε V(G)} of sets A(v) of cardinality a there exists a family {B(v)\v ε V(G)} of subsets B(v) A(v) of cardinality b such that B(u) B(v) =θ whenever uv E(G). It is Proved in this paper that every plane graph in which no two triangles share a common vertex is (4m, m)-choosable for every nonnegative integer m.

Girth and Circular Choosability of Series-Parallel Graphs

This paper discusses a circular version of choosability of series-parallel graphs. Let χe,l denote the circular choosability （or the circular list chromatic number）. This paper proves that serial-parallel graphs of girth at least 4n ＋ 1 have circular choosability at most 2＋1/n.

Acyclic 6-choosability of planar graphs without adjacent short cycles

A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).

On 3-choosability of triangle-free plane graphs

It is known that every triangle-free plane graph is 3-colorable.However,such a triangle-free plane graph may not be 3-choosable.In this paper,we prove that a triangle-free plane graph is 3-choosable if no 4-cycle in it is adjacent to a 4-or a 5-cycle.This improves some known results in this direction.

List Total Colorings of Planar Graphs without Triangles at Small Distance

Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-（△ ＋ 2）-choosable if （1） △ ≥ 7 and G has no adjacent triangles （i.e., no two triangles are incident with a common edge）; or （2） △ ≥6 and G has no intersecting triangles （i.e., no two triangles are incident with a common vertex）; or （3） △ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}.

Edge choosability of planar graphs without short cycles

In this paper we prove that if G is a planar graph with △= 5 and without 4-cycles or 6-cycles, then G is edge-6-choosable. This consequence together with known results show that, for each fixed k ∈{3,4,5,6}, a k-cycle-free planar graph G is edge-(△+ 1)-choosable, where △ denotes the maximum degree of G.

Acyclic Choosability of Graphs with Bounded Degree

An acyclic colouring of a graph G is a proper vertex colouring such that every cycle uses at least three colours. For a list assignment L = {L(v)| v∈V(G)}, if there exists an acyclic colouringρ such that ρ(v)∈L(v) for each v∈V(G), then ρ is called an acyclic L-list colouring of G. If there exists an acyclic L-list colouring of G for any L with |L(v)|≥k for each v∈V(G), then G is called acyclically k-choosable. In this paper, we prove that every graph with maximum degree Δ≤7 is acyclically 13-choosable. This upper bound is first proposed. We also make a more compact proof of the result that every graph with maximum degree Δ≤3(resp., Δ≤4) is acyclically 4-choosable(resp., 5-choosable).

Acyclic 6-choosability of Planar Graphs without 5-cycles and Adjacent 4-cycles

A proper vertex coloring of a graph is acyclic if every cycle uses at least three colors.A graph G is acyclically k-choosable if for any list assignment L={L(v):v∈V(G)}with|L(v)|≥k for all v∈V(G),there exists a proper acyclic vertex coloringφof G such thatφ(v)∈L(v)for all v∈V(G).In this paper,we prove that if G is a planar graph and contains no 5-cycles and no adjacent 4-cycles,then G is acyclically 6-choosable.

Weight Choosability of Graphs with Maximum Degree 4

Let k be a positive integer.A graph G is k-weight choosable if,for any assignment L(e)of k real numbers to each e∈E(G),there is a mapping f:E(G)→R such that f(uv)∈L(uv)and∑e∈∂(u)^f(e)≠∑e∈∂(u)^f(e)for each uv∈E(G),where?(v)is the set of edges incident with v.As a strengthening of the famous 1-2-3-conjecture,Bartnicki,Grytczuk and Niwcyk[Weight choosability of graphs.J.Graph Theory,60,242–256(2009)]conjecture that every graph without isolated edge is 3-weight choosable.This conjecture is wildly open and it is even unknown whether there is a constant k such that every graph without isolated edge is k-weight choosable.In this paper,we show that every connected graph of maximum degree 4 is 4-weight choosable.