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.展开更多
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 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...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.展开更多
Given a list assignment of L to graph G,assign a list L(υ)of colors to each υ∈V(G).An(L,d)^(*)-coloring is a mapping π that assigns a color π(υ)∈L(υ)to each vertex υ∈V(G)such that at most d neighbors of υ r...Given a list assignment of L to graph G,assign a list L(υ)of colors to each υ∈V(G).An(L,d)^(*)-coloring is a mapping π that assigns a color π(υ)∈L(υ)to each vertex υ∈V(G)such that at most d neighbors of υ receive the color υ.If there exists an(L,d)^(*)-coloring for every list assignment L with|L(υ)|≥k for all υ∈ V(G),then G is called to be(k,d)^(*)-choosable.In this paper,we prove every planar graph G without adjacent k-cycles is(3,1)^(*)-choosable,where k ∈{3,4,5}.展开更多
A graph G is called chromatic-choosable if its choice number is equal to its chromatic number, namely ch（G） = X（G）. Ohba＇s conjecture states that every graph G with 2X（G）＋ 1 or fewer vertices is chromatic- cho...A graph G is called chromatic-choosable if its choice number is equal to its chromatic number, namely ch（G） = X（G）. Ohba＇s conjecture states that every graph G with 2X（G）＋ 1 or fewer vertices is chromatic- choosable. It is clear that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. Recently, Kostochka, Stiebitz and Woodall showed that Ohba＇s conjecture holds for complete multipartite graphs with partite size at most five. But the complete multipartite graphs with no restriction on their partite size, for which Ohba＇s conjecture has been verified are nothing more than the graphs Kt＋3,2.（k-t-l）,l.t by Enotomo et al., and gt＋2,3,2.（k-t-2）,l.t for t ≤ 4 by Shen et al.. In this paper, using the concept of f-choosable （or Lo-size-choosable） of graphs, we show that Ohba＇s conjecture is also true for the graphs gt＋2,3,2.（k-t-2）,l.t when t ≥ 5. Thus, Ohba＇s conjecture is true for graphs Kt＋2,3,2,（k-t-2）,l＊t for all integers t 〉 1.展开更多
基金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 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
基金the Science Foundation of the Education Department of Hebei Province (2005108).
文摘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.
文摘Given a list assignment of L to graph G,assign a list L(υ)of colors to each υ∈V(G).An(L,d)^(*)-coloring is a mapping π that assigns a color π(υ)∈L(υ)to each vertex υ∈V(G)such that at most d neighbors of υ receive the color υ.If there exists an(L,d)^(*)-coloring for every list assignment L with|L(υ)|≥k for all υ∈ V(G),then G is called to be(k,d)^(*)-choosable.In this paper,we prove every planar graph G without adjacent k-cycles is(3,1)^(*)-choosable,where k ∈{3,4,5}.
基金Supported by the National Natural Science Foundation of China(No.10871058)the project for mathematical research from the Natural Science Foundation of Hebei Province,China(No.08M004)Hebei Normal University of Science and Technology,China(ZDJS2009 and CXTD2012)
文摘A graph G is called chromatic-choosable if its choice number is equal to its chromatic number, namely ch（G） = X（G）. Ohba＇s conjecture states that every graph G with 2X（G）＋ 1 or fewer vertices is chromatic- choosable. It is clear that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. Recently, Kostochka, Stiebitz and Woodall showed that Ohba＇s conjecture holds for complete multipartite graphs with partite size at most five. But the complete multipartite graphs with no restriction on their partite size, for which Ohba＇s conjecture has been verified are nothing more than the graphs Kt＋3,2.（k-t-l）,l.t by Enotomo et al., and gt＋2,3,2.（k-t-2）,l.t for t ≤ 4 by Shen et al.. In this paper, using the concept of f-choosable （or Lo-size-choosable） of graphs, we show that Ohba＇s conjecture is also true for the graphs gt＋2,3,2.（k-t-2）,l.t when t ≥ 5. Thus, Ohba＇s conjecture is true for graphs Kt＋2,3,2,（k-t-2）,l＊t for all integers t 〉 1.
