Coloration impropre des graphes planaires

Abstract

Une k−coloration t−frugale impropre d’un graphe G est une coloration des sommets de Gutilisant k couleurs tel que pour tout sommets v de Gaucune couleur n’apparait plus de t fois dans le voisinage de v. Le nombre chromatique t−frugal impropre, noté χ (G), est le plus petit entier k tel que G admet une k−coloration t−frugale impropre. Cette notion a été introduite par Bard en 2021. Dans ce mémoire, nous avons étudié le nombre chromatique t−frugal de certaines classes de graphes planaires. Mots-clé : coloration impropre - coloration frugale - nombre chromatique frugale - méthode de déchargement - graphe planaire.