图 G 被叫(k, d )*-choosable 如果为为所有 v V (G) 的每表任务 L 令人满意的 | L (v)|=k,有 G 的 L 着色以便 G 的每个顶点至多有与象自己的一样的颜色有颜色的 d 邻居。在这份报纸,没有 6 电路和邻近自己或四角形的一个三角形的...图 G 被叫(k, d )*-choosable 如果为为所有 v V (G) 的每表任务 L 令人满意的 | L (v)|=k,有 G 的 L 着色以便 G 的每个顶点至多有与象自己的一样的颜色有颜色的 d 邻居。在这份报纸,没有 6 电路和邻近自己或四角形的一个三角形的每张平面图是,这被显示出(3,1 )*-choosable。展开更多
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 suc...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).展开更多
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 (△ + 1)-choosable, where△ denotes the maximum degree ...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 (△ + 1)-choosable, where△ denotes the maximum degree of G.展开更多
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)...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).展开更多
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∈...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.展开更多
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 pro...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.展开更多
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 ...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.展开更多
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...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.展开更多
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 l...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展开更多
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 ...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.展开更多
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 suc...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.展开更多
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 c...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}.展开更多
基金Supported by the Natural Science Research Project of Ordinary Universities in Jiangsu(08KJB110002)Supported by the Program for ETHYTC(08QNZCK03)Supported by the NSFC(10671095)
文摘图 G 被叫(k, d )*-choosable 如果为为所有 v V (G) 的每表任务 L 令人满意的 | L (v)|=k,有 G 的 L 着色以便 G 的每个顶点至多有与象自己的一样的颜色有颜色的 d 邻居。在这份报纸,没有 6 电路和邻近自己或四角形的一个三角形的每张平面图是,这被显示出(3,1 )*-choosable。
基金supported by National Natural Science Foundation of China (Grant Nos. 11071223 and 11101377)Natural Science Foundation of Zhejiang Province,China (Gran No. Z6090150)+1 种基金Zhejiang Innovation Project (Grant No. T200905)Zhejiang Normal University Innovation Team Program
文摘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).
基金supported partially by the National Natural Science Foundation of China(Grant No.10471 131)the Natural Science Foundation of Zhejiang Province(Grant No.M103094)
文摘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 (△ + 1)-choosable, where△ denotes the maximum degree of G.
基金Supported by National Natural Science Foundation of China(Grant Nos.11771443 and 11601510)Shandong Province Natural Science Foundation(Grant No.ZR2017QF011)。
文摘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).
基金Supported by National Natural Science Foundation of China(Grant Nos.11871397 and 11971205)the Natural Science Basic Research Plan in Shaanxi Province of China(Grant No.2020JM-083)the Fundamental Research Funds for the Central Universities(Grant No.3102019ghjd003)。
文摘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.
基金Supported by Guangdong Province Basic and Applied Basic Research Foundation and Joint Foundation Project(Grant No.2019A1515110324)Natural Science Foundation of Guangdong province(Grant No.2019A1515011031)University Characteristic Innovation Project of Guangdong province(Grant No.2019KTSCX092)。
文摘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.
基金This research is supported by the Postdoctoral Fund of China and the K.C.W. Education Fund of HongKong.
文摘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.
基金Supported by the Science and Technology Foundation of Zhejiang University(1 0 70 0 0 - 54430 1 )
文摘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.
基金supported by the National Natural Science Foundation of China(1 0 0 0 1 0 35)
文摘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
基金NSFC(Grant Nos.12101285,12171222)Basic and Applied Basic Research Foundation and Jointof Guangdong Province,China(Grant No.2019A1515110324)+1 种基金Guangdong Basic and Applied Basic Research Foundation(Natural Science Foundation of Guangdong Province,China,Grant No.2021A1515010254)Foundation of Lingnan Normal University(Grant Nos.ZL2021017,ZL1923)。
文摘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.
基金supported by National Natural Science Foundation of China(Grant No.11001055)supported by National Natural Science Foundation of China(Grant No.60672030)Natural Science Foundation of Fujian Province(Grant Nos.2010J05004 and 2011J06001)
文摘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.
文摘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}.