Title of article :
Improper choosability of graphs of nonnegative characteristic
Author/Authors :
Yongzhu Chen، نويسنده , , Weiyi Zhu، نويسنده , , Weifan Wang، نويسنده ,
Issue Information :
دوهفته نامه با شماره پیاپی سال 2008
Abstract :
A graph G is called (k,d)*-choosable if, for every list assignment L with L(v)=k for all v V(G), there is an L-coloring of G such that every vertex has at most d neighbors having the same color as itself.
Let G be a graph embeddable in a surface of nonnegative characteristic. In this paper, we prove: (1) If G contains no k-cycle with a chord for all k=4,5,6, then G is (3,1)*-choosable; (2) If G contains neither 5-cycle with a chord nor 6-cycle with a chord, then G is (4,1)*-choosable.
Keywords :
Cycle , Chord , Characteristic , Graph , Improper choosability
Journal title :
Computers and Mathematics with Applications
Journal title :
Computers and Mathematics with Applications