Geodesic
Defective choosability of graphs in surfaces
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 441-459

Voir la notice de l'article provenant de la source Library of Science

It is known that if G is a graph that can be drawn without edges crossing in a surface with Euler characteristic ε, and k and d are positive integers such that k ≥ 3 and d is sufficiently large in terms of k and ε, then G is (k,d)*-colorable; that is, the vertices of G can be colored with k colors so that each vertex has at most d neighbors with the same color as itself. In this paper, the known lower bound on d that suffices for this is reduced, and an analogous result is proved for list colorings (choosability). Also, the recent result of Cushing and Kierstead, that every planar graph is (4,1)*-choosable, is extended to K_3,3-minor-free and K₅-minor-free graphs.
Keywords: list coloring, defective coloring, minor-free graph 
@article{DMGT_2011_31_3_a2,
     author = {Woodall, Douglas},
     title = {Defective choosability of graphs in surfaces},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {441--459},
     publisher = {mathdoc},
     volume = {31},
     number = {3},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a2/}
}
TY  - JOUR
AU  - Woodall, Douglas
TI  - Defective choosability of graphs in surfaces
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 441
EP  - 459
VL  - 31
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a2/
LA  - en
ID  - DMGT_2011_31_3_a2
ER  - 
%0 Journal Article
%A Woodall, Douglas
%T Defective choosability of graphs in surfaces
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 441-459
%V 31
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a2/
%G en
%F DMGT_2011_31_3_a2
Woodall, Douglas. Defective choosability of graphs in surfaces. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 441-459. http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a2/