Ohba’s conjecture for graphs with independence number five |
| |
| Authors: | Alexandr V Kostochka Michael Stiebitz Douglas R Woodall |
| |
| Institution: | 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 等数据库收录！ |
|
