Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
472344 | Computers & Mathematics with Applications | 2008 | 6 Pages |
Abstract
A graph GG is called (k,d)∗(k,d)∗-choosable if, for every list assignment LL with |L(v)|=k|L(v)|=k for all v∈V(G)v∈V(G), there is an LL-coloring of GG such that every vertex has at most dd neighbors having the same color as itself.Let GG be a graph embeddable in a surface of nonnegative characteristic. In this paper, we prove: (1) If GG contains no kk-cycle with a chord for all k=4,5,6k=4,5,6, then GG is (3,1)∗(3,1)∗-choosable; (2) If GG contains neither 5-cycle with a chord nor 6-cycle with a chord, then GG is (4,1)∗(4,1)∗-choosable.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Yongzhu Chen, Weiyi Zhu, Weifan Wang,