Graphes représentables par mot

Abstract

Les principaux objectifs de ce travail sont de présenter les graphes représentables par mot et les graphes τ –représentables, i.e. les graphes dont un représentant évite le motif τ de longueur au moins 3. Rappelons tout d’abord qu’un graphe est représentable par mot s’il existe un mot tel que deux lettres s’alternent dans ce mot si et seulement si les sommets correspondants sont adjacents. On dit que deux lettres x et y s’alternent dans un mot si, lorsqu’on a supprimé du mot les symboles distincts de x et y, il n’apparait aucun facteur xx ou yy. Nous montrons qu’un graphe est représentable par mot si et seulement si il existe un naturel k tel qu’un mot k-uniforme représente ce graphe. De plus, nous établissons que ce représentant est 2-uniforme si et seulement si le graphe considéré est un graphe circulaire et nous construisons des graphes non-représentables. Nous prouvons que, lorsqu’il est restreint aux graphes représentables, le problème de la clique maximale, connu pour être NP-complet, est résoluble en un temps polynomial. Enfin, nous introduisons la notion de graphes τ -représentables et nous nous attardons sur les graphes µ-représentables, où µ est une permutation de S_3. Nous établissons que de tels graphes sont nécessairement des graphes circulaires et nous démontrons que la réciproque est fausse, c’est-à-dire qu’il existe des graphes circulaires qui ne sont pas µ-représentables.

The main objectives of this work are to present word-representable graphs and τ –representable graphs, i.e. graphs where a representative avoids the τ pattern of length at least 3. First of all, let us remember that a graph is word-representable if there is a word such that two letters alternate in this word if and only if the corresponding vertices are adjacent. It is said that two letters x and y alternate in a word if, after removing the separate symbols of x and y from the word, no factor xx or yy appears. We show that a graph is word-representable if and only if there is a natural k such that a k-uniform word represents this graph. In addition, we establish that this representative is 2-uniform if and only if the considered graph is a circle graph and we construct non-word-representable graphs. We prove that, when restricted to word-representable graphs, the problem of maximum clique, known as NP-complete, is resolvable in a polynomial time. Finally, we introduce the notion of τ –representable graphs and we focus on µ-representable graphs, where µ is a permutation of S_3. We establish that such graphs are necessarily circle graphs and we show that the reciprocal is false, i.e. that there exist circle graphs that are not µ-representable.