Coloration d’incidences des graphes planaires

Abstract

Résumé : Une incidence d’un graphe G est un couple (u, e) où u est un sommet de G et e une arête de G incidente au sommet u. Deux incidences (u, e) et (v, f) sont adjacentes si elles sont distinctes et que u = v ou e = f ou uv = e ou uv = f. Une k-coloration d’incidences d’un graphe G est une application de l’ensemble des incidences de G dans l’ensemble C de k couleurs telle que deux incidences adjacentes aient des couleurs différentes. Le nombre chromatique d’incidences, noté χ (G), est le plus petit entier k tel que G admet une k-coloration d’incidences. Cette notion a été introduite par Brualdi et Massey (1993), puis étudiée depuis par de nombreux chercheurs. Dans ce mémoire, nous prouvons que tout graphe planaire de degré maximum au plus 4 et sans cycles de longueurs 4 et 5 admet une 7-coloration d’incidences. i Mots-clé : Graphe planaire - Méthode de déchargement - nombre chromatique d’incidences Coloration d’incidences.