On choosability of some complete multipartite graphs and Ohba's conjecture

详细信息	查看全文 | 推荐本文 |

• 作者：Yufa Shen ; Wenjie He ; Guoping Zheng ; Yanning Wang ; Lingmin Zhang
• 关键词：List coloring ; Complete multipartite graphs ; Chromatic-choosable graphs ; Ohba's conjecture
• 刊名：Discrete Mathematics
• 出版年：2008
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 January 2008
• 卷：308
• 期：1
• 页码：136-143
• 文件大小：189 K

摘要

A graph G is said to be chromatic-choosable if 4NDDM4X-3&_mathId=mml1&_user=10&_cdi=5632&_rdoc=12&_acct=C000050221&_version=1&_userid=10&md5=b313f9b0c4d02d9025b411dbbf17ce44" title="Click to view the MathML source">ch(G)=χ(G). Ohba has conjectured that every graph G with 4NDDM4X-3&_mathId=mml2&_user=10&_cdi=5632&_rdoc=12&_acct=C000050221&_version=1&_userid=10&md5=68790dad9aa3e0bbca001a167c2c1622" title="Click to view the MathML source">2χ(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. But for complete multipartite graphs, the graphs for which Ohba's conjecture has been verified are nothing more than 4NDDM4X-3&_mathId=mml3&_user=10&_cdi=5632&_rdoc=12&_acct=C000050221&_version=1&_userid=10&md5=79eee80ecaa87c0b035798ee5c0f4844" title="Click to view the MathML source">K_{3*2,2*(k-3),1}, 4">4NDDM4X-3&_mathId=mml4&_user=10&_cdi=5632&_rdoc=12&_acct=C000050221&_version=1&_userid=10&md5=734392c2dd0ce0248829e483f342a825" title="Click to view the MathML source">K_3,2*(k-1), and 4NDDM4X-3&_mathId=mml5&_user=10&_cdi=5632&_rdoc=12&_acct=C000050221&_version=1&_userid=10&md5=294ac3bbaab046c04bab27fffafca154" title="Click to view the MathML source">K_{s+3,2*(k-s-1),1*s}. These results have been obtained indirectly from the investigation about complete multipartite graphs by Gravier and Maffray and by Enomoto et al. In this paper we show that Ohba's conjecture is true for complete multipartite graphs 4NDDM4X-3&_mathId=mml6&_user=10&_cdi=5632&_rdoc=12&_acct=C000050221&_version=1&_userid=10&md5=867dd398804c056dc15d89fb74721315" title="Click to view the MathML source">K_{4,3,2*(k-4),1*2} and 4NDDM4X-3&_mathId=mml7&_user=10&_cdi=5632&_rdoc=12&_acct=C000050221&_version=1&_userid=10&md5=1228537becb985a251a2bde079497350" title="Click to view the MathML source">K_{5,3,2*(k-5),1*3}. By the way, we give some discussions about a result of Enomoto et al.