Coloriages non répétitifs de graphes

Abstract

Un coloriage de graphe consiste à attribuer une couleur aux sommets (ou aux arêtes) d’un graphe en respectant certaines conditions. Dans ce travail, nous nous intéressons aux coloriages non répétitifs, c’est-à-dire les coloriages dont la suite des couleurs des sommets de n’importe quel chemin de longueur paire ne forme pas un carré. Nous cherchons alors le nombre minimum de couleurs nécessaires à un coloriage non répétitif pour certaines classes de graphes, ou du moins une borne. Nous considérons également un autre coloriage défini de manière similaire où nous ne tenons plus compte des chemins, mais des pistes. De plus, nous étudions brièvement les coloriages des arêtes. Enfin, nous généralisons la définition de coloriages non répétitifs en k blocs, et nous donnons le nombre minimum de couleurs nécessaires à un coloriage sans cube pour les chemins et les cycles.

Graph coloring is an assignment of color to vertices (or edges) of a graph under some conditions. In this paper, we are interested in nonrepetitive colorings, which are colorings where the vertices colors of each path with even length does not form a square. Then, we search the minimum number of colors needed for a nonrepetitive coloring for some class of graphs, or at least a bound. We also consider an other coloring defined similarly based on walks instead of paths. Moreover, we briefly study edges colorings. Finally, we generalize the definition of nonrepetitive coloring in k blocs, and we give the minimum number of colors needed for a cube-free coloring for paths and cycles.