Une coloration par listes est d-impropre si chaque sommet a au plus
d voisins de sa couleur. Un graphe est m-choisissable avec
impropreté d s'il existe une coloration par listes d-impropre
pour toute liste autorisant au moins m couleurs pour chaque
sommet. Le degré moyen maximum d'un graphe est le maximum des
degrés moyens de ses sous-graphes.
La NP-Complétude de la coloration impropre est claire dans le cas
général. Nous étudierons la complexité lorsque l'on borne le
degré à l'aide de la borne de Lovász.
Nous nous intéresserons ensuite a la choisissabilité impropre des
graphes planaires. Nous verrons en particulier les résultats connus
sur la 2-choisissabilité des graphes planaires de maille
minorée. Or, le degré moyen maximum d'un graphe planaire est
borné en fonction de sa maille. Il est ainsi naturel de
s'interroger sur les rôles respectifs de la planarité et du
degré moyen maximum. Nous montrerons que les resultats connus sur la
2-choisissabilite impropre des graphes planaires de maille fixée
ne font en réalité intervenir que le degré moyen maximum, et
nous les améliorerons.