Résumé:
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.
