Feedback

Faculté des Sciences
Faculté des Sciences
MASTER THESIS
VIEW 79 | DOWNLOAD 21

Coloriages non répétitifs de graphes

Download
Parlascino, Alessia ULiège
Promotor(s) : Rigo, Michel ULiège
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 ULiège
Date of defense  : 2-Jul-2019/3-Jul-2019
Advisor(s) : Rigo, Michel ULiège
Committee's member(s) : Charlier, Emilie ULiège
Leroy, Julien ULiège
Swan, Yvik ULiège
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)

File
Access Memoire_Parlascino_Alessia.pdf
Description:
Size: 816.92 kB
Format: Adobe PDF

Author

  • Parlascino, Alessia ULiège Université de Liège > Master sc. math., à fin.

Promotor(s)

Committee's member(s)

  • Total number of views 79
  • Total number of downloads 21










All documents available on MatheO are protected by copyright and subject to the usual rules for fair use.
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.