Coloriages non répétitifs de graphes
Parlascino, Alessia
Promotor(s) : Rigo, Michel
Date of defense : 2-Jul-2019/3-Jul-2019 • Permalink : http://hdl.handle.net/2268.2/6989
Details
Title : | Coloriages non répétitifs de graphes |
Author : | Parlascino, Alessia |
Date of defense : | 2-Jul-2019/3-Jul-2019 |
Advisor(s) : | Rigo, Michel |
Committee's member(s) : | Charlier, Emilie
Leroy, Julien Swan, Yvik |
Language : | French |
Number of pages : | 89 |
Keywords : | [fr] Théorie des graphes [fr] Coloriages non répétitifs [fr] Mots sans carré [en] Nonrepetitive coloring [en] Squarefree coloring [en] Squarefree word |
Discipline(s) : | Physical, chemical, mathematical & earth Sciences > Mathematics |
Target public : | Researchers Professionals of domain Student |
Institution(s) : | Université de Liège, Liège, Belgique |
Degree: | Master en sciences mathématiques, à finalité didactique |
Faculty: | Master thesis of the Faculté des Sciences |
Abstract
[fr] 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.
[en] 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.
File(s)
Document(s)
Cite this master thesis
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.