| Résumé | Une coloration k-frugale des sommets d'un graphe est une coloration propre (deux sommets adjacents ont des couleurs distinctes) telle que dans chaque voisinage, chaque couleur apparait au plus k fois. Par exemple une coloration 1-frugale d'un graphe G est exactement une coloration propre du carré de G. On s'intéresse à la coloration frugale des graphes planaires, ainsi qu'à la coloration frugale des arêtes des multigraphes. Ces problèmes sont reliés au L(p,q)-labelling, à la coloration du carré des graphes, et à la coloration cyclique des graphes planaires.
(travail en collaboration avec Omid Amini et Jan van den Heuvel) |