Choice number of complete multipartite graphs
Choice number of complete multipartite graphs
复制标题
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Wenjie He;Lingmin Zhang;D. Cranston;Yufa Shen;Guoping Zheng
中科院分区：
文献类型：
--
作者：
Wenjie He;Lingmin Zhang;D. Cranston;Yufa Shen;Guoping Zheng
如果图G的选择数等于其色数，即Ch（G）= χ（G），则称图G是色可选择的. Ohba证明了每个图G满足|V（G）|≤ 2χ（G）+1是色可选择的。由于每个k-色图都是一个完全k-部图的子图，我们看到Ohba猜想成立当且仅当它对每个完全多部图成立。然而，大场猜想唯一被证实的完全多部图是：K3 <$2，2 <$（k−3），1，K3，2 <$（k−1），Ks+3，2 <$（k−s−1），1 <$s，K4，3，2 <$（k−4），1 <$2和K5，3，2 <$（k−5），1 <$3。在本文中，我们证明了Ohba猜想是正确的两个新的类的完全多部图：图与三个部分的大小为3和图与一个部分的大小为4和两个部分的大小为3。也就是说，我们证明了Ch（K3 <$3，2 <$（k−5），1 <$2）= k和Ch（K4，3 <$2，2 <$（k−6），1 <$3）= k（分别对k ≥ 5和k ≥ 6）。
A graph G is called chromatic-choosable if its choice number is equal to its chromatic number, namely Ch(G) = χ(G). Ohba has conjectured that every graph G satisfying |V (G)| ≤ 2χ(G)+1 is chromatic-choosable. Since each k-chromatic graph is a subgraph of a complete k-partite graph, we see that Ohba’s conjecture is true if and only if it is true for every complete multipartite graph. However, the only complete multipartite graphs for which Ohba’s conjecture has been verified are: K3∗2,2∗(k−3),1, K3,2∗(k−1), Ks+3,2∗(k−s−1),1∗s, K4,3,2∗(k−4),1∗2, and K5,3,2∗(k−5),1∗3. In this paper, we show that Ohba’s conjecture is true for two new classes of complete multipartite graphs: graphs with three parts of size 3 and graphs with one part of size 4 and two parts of size 3. Namely, we prove that Ch(K3∗3,2∗(k−5),1∗2) = k and Ch(K4,3∗2,2∗(k−6),1∗3) = k (for k ≥ 5 and k ≥ 6, respectively).