List Colouring When The Chromatic Number Is Close To the Order Of The Graph期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

List Colouring When The Chromatic Number Is Close To the Order Of The Graph

Authors:	Email author" target="_blank">Bruce?Reed Email author Benny?Sudakov?

Institution:	(1) CNRS, Paris, France;(2) School of Computer Science, McGill University, Montreal, Quebec, H3A2A7, Canada;(3) Department of Mathematics, Princeton University, Princeton, NJ 08540, USA;(4) Institute for Advanced Study, Princeton, NJ 08540, USA

Abstract:	Ohba has conjectured 7] that if G has 2(G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture obtained by replacing 2(G)+1 by $\frac{5} {3}\chi {\left( G \right)} - \frac{4} {3}.$ * This research was partially supported by DIMACS and by CNRS/NSF collaboration grant. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey.

Keywords:	05C15 05D40
本文献已被 SpringerLink 等数据库收录！