Ohba’s conjecture for graphs with independence number five |
| |
Authors: | Alexandr V. Kostochka Michael Stiebitz Douglas R. Woodall |
| |
Affiliation: | aDepartment of Mathematics, University of Illinois, Urbana, IL, 61801, USA;bSobolev Institute of Mathematics, Novosibirsk, Russia;cInstitute of Mathematics, Technische Universität Ilmenau, D-98684 Ilmenau, Germany;dSchool of Mathematical Sciences, University of Nottingham, Nottingham, NG7 2RD, UK |
| |
Abstract: | Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices. |
| |
Keywords: | Chromatic number Vertex coloring List coloring List chromatic number Choosability Complete multipartite graph |
本文献已被 ScienceDirect 等数据库收录! |
|