Contribution à l’étude du problème L(3, 2, 1)-étiquetage des graphes planaires

Abstract

Un k-L(3, 2, 1)-étiquetage d'un graphe G = (V,E) est une application ƒ de l'ensemble des sommets V vers l'ensemble des entiers {0,1,..., k} telle que pour tout x, y Є V, f(x) f(y)|≥ 4 - d(x, y), où d(x, y) représente la distance entre les sommets æ et y, et 1≤d(x, y) < 3. Le nombre L(3, 2, 1)-étiquetage de G, noté A3,2,1 (G), est le plus petit nombre k tel que G ait un k-L(3, 2, 1)-étiquetage. Dans [34], Lui et Shao ont montré que le A3,2,1(G) de tout graphe planaire G de degré maximum ▲ est au plus égal à 15(A2 – ▲ + 1). Dans ce travail, nous améliorons ce résultat pour les graphes planaires de degré maximum au moins 12, les graphes planaires extérieurs et les graphes Halin cubiques. De plus, nous étudions le A3,2,1(G) de tout graphe G ayant un degré moyen maximum borné par 9/4. Mots-clé : Graphe planaire - L(p, q)-étiquetage - Nombre d'étiquetage - L(3, 2, 1)-étiquetage.