Improper choosability of graphs of nonnegative characteristic ?
A graph G G is called (k,d)? ( k , d ) ? -choosable if, for every list assignment L L with |L(v)|=k | L ( v ) | = k for all v?V(G) v ? V ( G ) , there is an L L -coloring of G G such that every vertex has at most d d neighbors having the same color as itself. Let G G be a graph embeddable in a surface of nonnegative characteristic. In this paper, we prove: (1) If G G contains no k k -cycle with a chord for all k=4,5,6 k = 4 , 5 , 6 , then G G is (3,1)? ( 3 , 1 ) ? -choosable; (2) If G G contains neither 5-cycle with a chord nor 6-cycle with a chord, then G G is (4,1)? ( 4 , 1 ) ? -choosable.
improper choosability graph characteristic chord cycle