Choice number of some complete multi-partite graphs

Autor:	Junko Sakamoto, Kyoji Ohba, Hikoe Enomoto, Katsuhiro Ota
Rok vydání:	2002
Předmět:	Discrete mathematics Complete multi-partite graphs Conjecture 1-planar graph Graph List coloring Theoretical Computer Science Combinatorics Choice number Indifference graph Pathwidth Chordal graph Discrete Mathematics and Combinatorics Chromatic scale Mathematics
Zdroj:	Discrete Mathematics. 244(1-3):55-66
ISSN:	0012-365X
DOI:	10.1016/s0012-365x(01)00059-0
Popis:	One of the authors has conjectured that every graph G with 2χ(G)+1 or fewer vertices is χ(G)-choosable. Motivated by this, we investigate the choice numbers of some complete k-partite graphs of order slightly larger than 2k, and settle the conjecture for some special cases. We also present several complete multi-partite graphs whose choice numbers are not equal to their chromatic numbers.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4efb6ca95a11d9038c44a585a3a4a5bb Zobrazit plný text záznamu Full Text from ScienceDirect