Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1709555 | Applied Mathematics Letters | 2009 | 5 Pages |
A graph GG is said to be chromatic-choosable if its choice number is equal to its chromatic number. Ohba has conjectured that every graph GG with 2χ(G)+12χ(G)+1 or fewer vertices is chromatic-choosable. At present, only several special classes of graphs have been verified, for which Ohba’s conjecture is true. In 2004, Ohba proved that if |V(G)|≤2χ(G)|V(G)|≤2χ(G) and the independence number of GG is at most 3, then GG is chromatic-choosable (Ars Combinatoria, 72 (2004), 133–139). In this work we show that if |V(G)|≤2χ(G)+1|V(G)|≤2χ(G)+1 and the independence number of GG is at most 3, then GG is chromatic-choosable. This proves that Ohba’s conjecture is true for all graphs GG with independence number at most 3 and all χ(G)χ(G)-chromatic subgraphs of GG.