کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1709555 | 1012856 | 2009 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Ohba’s conjecture is true for graphs with independence number at most three Ohba’s conjecture is true for graphs with independence number at most three](/preview/png/1709555.png)
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.
Journal: Applied Mathematics Letters - Volume 22, Issue 6, June 2009, Pages 938–942