Résumé | Une coloration quasi propre est une coloration des sommets où chaque classe de couleurs induit un sous graphe de degré maximum fixé. Dans cet exposé, nous nous intéresserons au cas où les couleurs sont de deux types: a couleurs induisant un sous graphe de degré maximum d, et b couleurs induisant un stable (coloration propre): on parle de (d,a,b)*-coloration. Nous montrons que tout graphe dont le mad (degré moyen maximum) est inférieur à une certaine fonction f est (d,a,b)*-coloriable. Cette fonction f tend (par valeurs inférieures) vers 2a+b quand d tend vers l'infini. Ce résultat est asymptotiquement optimal : il existe des graphes non (d,a,b)*-coloriables dont le mad tend (par valeurs inférieures également) vers 2a+b. Ceci montre en quelque sorte qu'en terme de degré moyen, une couleur d-impropre n'est pas plus efficace que deux couleurs propres. |