Ohba's conjecture is true for graphs with independence number at most three
Ohba's conjecture is true for graphs with independence number at most three
复制标题
大场猜想对于独立数最多为 3 的图成立
DOI：
10.1016/j.aml.2009.01.001
复制
发表时间：
2009-06
影响因子：
3.7
通讯作者：
Yufa shen
中科院分区：
文献类型：
--
作者：
Yanpo Li;GuopingZheng;Wenjie He;Yufa shen
如果一个图G的选择数等于它的色数，则称它是色可选的。Ohba猜想，每个有2个χ(G)+1个或更少顶点的图G是色可选的。目前，只有几类特殊的图被证明，Ohba猜想是正确的。2004年，Ohba证明了如果|V(G)|≤2χ(G)且G的独立数至多为3，则G是色可选的(Ars Combinatoria，72(2004)，133-139)。证明了如果|V(G)|≤2χ(G)+1且G的独立数至多为3，则G是色可选的。这证明了Ohba猜想对所有独立数不超过3的图G和G的所有χ(G)-色子图都成立。
A graph G is said to be chromatic-choosable if its choice number is equal to its chromatic number. Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. At present, only several special classes of graphs have been verified, for which Ohba’s conjecture is true. In 2004, Ohba proved that if |V(G)|≤2χ(G) and the independence number of G is at most 3, then G is chromatic-choosable (Ars Combinatoria, 72 (2004), 133–139). In this work we show that if |V(G)|≤2χ(G)+1 and the independence number of G is at most 3, then G is chromatic-choosable. This proves that Ohba’s conjecture is true for all graphs G with independence number at most 3 and all χ(G)-chromatic subgraphs of G.
登录
查看更多内容
DOI：
10.1016/j.disc.2007.03.059
发表时间：
2008
期刊：
Discret. Math.
影响因子：
--
作者：
Yufa Shen;Wenjie He;Guoping Zheng;Yanning Wang;Lingmin Zhang
通讯作者：
Yufa Shen;Wenjie He;Guoping Zheng;Yanning Wang;Lingmin Zhang
影响因子：
1.1
作者：
B. Reed;B. Sudakov
通讯作者：
B. Reed;B. Sudakov
影响因子：
0.9
作者：
K. Kawarabayashi;K. Ota;Akira Saito
通讯作者：
K. Kawarabayashi;K. Ota;Akira Saito
DOI：
10.1002/(sici)1097-0118(199802)27:2
发表时间：
1998-02
期刊：
J. Graph Theory
影响因子：
--
作者：
Sylvain Gravier;Frédéric Maffray
通讯作者：
Sylvain Gravier;Frédéric Maffray
DOI：
--
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Wenjie He;Lingmin Zhang;D. Cranston;Yufa Shen;Guoping Zheng
通讯作者：
Wenjie He;Lingmin Zhang;D. Cranston;Yufa Shen;Guoping Zheng