Méthode de déchargement appliquée aux problèmes de colorations injectives des graphes

Abstract

Dans ce travail, nous avons étudié la coloration injective des graphes en utilisant la méthode de déchargement. Aprés avoir expliqué le principe du raisonnement par déchargement, nous l’avons appliqué pour démontrer quelques propriétés des graphes planaires. Nous nous sommes par la suite intéresser à la recherche de l’indice chromatique injectif des graphes subcubiques de degré moyen maximum borné, ceci nous a permis de déduire une borne supérieure de l’indice chromatique des graphes planaires subcubiques de maille au moins 18. Mots clés : graphe - graphe planaire - coloration injective - degré moyen maximum méthode de déchargement. In this work, we have studied the injective coloring of graphs by using the discharging method. After given the principle of the discharging method, we give some example to proof some structuel properties of planar graphs. Next, we have considered the upper bound of the chromatic injective index of subcubic graph in term of maximum average degree, which give us an upper bound of the chromatic injectif index of subcubics planars graphs with the girth at least 18. Key words : graph - planar graph - injective coloring - maximum average degree - discharging method.