| Résumé | On considère une coloration impropre des graphes, dans laquelle chaque classe de couleur a un degré max borné. On étudie la coloration acyclique impropre par listes de certaine classes de graphes et on montre par exemple que les graphes planaires extérieurs sont acycliquement (2,5)-choosable (i.e. 2-choosable avec des classes de couleur de degré max au plus 5) et que les graphes de degré max. 3 sont acycliquement (3,1)-choosable. On donne aussi un lien entre cette coloration et la conjecture de Borodin et al "les graphes planaires sont acycliquement 5-choosable".
|