Since Septembre 2017, I teach at Polytech Montpellier. I am head of the Transversal Computer Science Department (« Pôle transversal informatique ») at Polytech Montpellier. I teach information technology and network tools, databases, algorithms, computer programming, and graph theory. All the course materials are available on the learning plateform Moodle.

For my previous teachings, follow this link.

1. Homomorphisms of signed graphs
   View DetailsHide Details

   Co-supervised by M. Montassier and A. Pinlou
   Student: Fabien Jacques (Master 2 - Univ. Bordeaux)

   With the Four Color Theorem playing a central role in the development of Graph Theory, the notions of minor and coloring have been branded as two of the most distinguished concepts in Graph Theory. The geometric notion of planarity has given birth to the theory of minors among others, and the coloring notion has proven to have an algebraic nature through its extension to the theory of graph homomorphisms.

   However, the correlation of minors and colorings remains somehow mysterious. The Four Color Theorem itself, in a slightly stronger form, claims that if a complete graph on five vertices cannot be formed by minor operation from a given graph, then the graph can be homomorphically mapped into the complete graph on four vertices (thus a 4-coloring). Commonly regarded as the most challenging conjecture in Graph Theory, the Hadwiger conjecture claims that five and four in this theorem can be replaced with $n$ and $n − 1$, respectively, for any value of $n$.

   The correlation of these two concepts has been difficult to study, mainly for the following reason: While coloring or homomorphism problems take roots into intersections of odd-cycles, the minor operation is irrelevant of the parity of cycles. Indeed contraction of an edge interchanges the parity of each cycle it contains! To overcome this barrier, the notion of signed graphs has been used implicitly since 1970s when coloring results on graphs with no odd-$K_4$ is proved, following which a stronger form of the Hadwiger conjecture, known as Odd Hadwiger conjecture, was proposed by Seymour and Gerards, independently.

   Observing the importance, and guided by some earlier works, in particular that of Guenin, we propose to study algebraic concepts (coloring and homomormphisms) for signed graphs.

2. $r$-hued coloring and $2$-distance coloring of graphs
   View DetailsHide Details

   Co-supervised by Mickaël Montassier and Alexandre Pinlou
   Student: Hoang La (Master 2 – ENS Lyon)

   In this internship, we propose to focus on two notions of colorings: r-hued coloring and 2-distance coloring.

3. Graph colorings and probabilistic methods
   View DetailsHide Details

   Co-supervised by Daniel Gonçalves and Alexandre Pinlou
   Student: Charles Guille-Escuret (Licence 3 – ENS Cachan)

   Une coloration de graphe est dite « propre » lorsque les sommets adjacents ont des couleurs différentes. Ceci revient à demander à ce que chaque couleur induise un graphe stable (sans arêtes). Il existe différentes variantes de colorations pour lesquelles on demande également à ce que chaque paire de couleurs induise une certaine famille de graphe (par exemple une forêt, une forêt d’étoiles, …). Aravind et Subramanian [1] ont considéré la généralisation suivante : pour une famille $F=\{H_1, H_2,...\}$ de graphes (bipartis et connexes), on définit la coloration dont les contraintes sont :

   • chaque couleur induit un stable, et
   • pour chaque paire de couleurs, le graphe induit par cette paire de couleurs ne contient aucun des graphes de $F$.

   En utilisant la notion de graphe aléatoire (chaque arête est présente avec probabilité $p$), les auteurs ont montré que, pour certains graphes de degrés maximum $\Delta$, colorier ces graphes ainsi nécessite au moins $O(\frac{\Delta^{\frac{m}{m-1}}}{(log \Delta)^{\frac1m}})$, où $m$ est le nombre d’arêtes du plus petit graphe de $F$.

   Aravind et Subramanian [2] ont également montré (en utilisant le lemme local de Lovasz) que ceci est le bon ordre de grandeur, i.e. que $O(\Delta^{\frac{m}{m-1}})$ couleurs suffisent.

   Ce problème est donc relativement clos. Cependant en utilisant la récente méthode dite de « compression d’entropie », il est possible d’améliorer la constante devant $\Delta^{\frac{m}{m-1}}$. Cette méthode permet non seulement d’améliorer de nombreux résultats auparavant obtenus par le lemme local de Lovasz, mais elle permet aussi d’en simplifier les preuves. Nous proposons donc, à l’aide de cette méthode, d’aborder le problème des colorations de graphes pour lesquels les contraintes portent également sur les triplet de couleurs (et éventuellement les $t$-uplets). Ce cas est relativement ouvert puisque peu de familles F ont été considérées, et qu’on ne dispose pas de bornes (inf ou sup) très intéressantes en fonction de $\Delta$.

   [1] NR Aravind, CR Subramanian
   Bounds on vertex colorings with restrictions on the union of color classes

   [2] NR Aravind, CR Subramanian
   Forbidden subgraph coloring and the oriented chromatic number

4. Albertson and Berman's conjecture
   View DetailsHide Details

   Co-supervised by Mickaël Montassier and Alexandre Pinlou
   Student: François Dross (Master 2 - ENS Lyon)

   The aim of this project is to study the following conjecture of Albertson and Berman:
   Conjecture [Albertson and Berman, 1976]. Every planar graph admits an induced subgraph on at least half of the vertices that is a forest.

   Some details on this conjecture can be found on the page of Douglas West.

   Firstly, the student will make a state of the art knowing that this problem have several names: decycling number, feedback vertex set, ...
   Secondly, we will work on a generalization of a formula of Alon, Mubayi, and Thomas concerning sparse graphs.

   Some references:

   • L.Kowalik, B. Luzar and R. Skrekovski. An improved bound on the largest induced forests for triangle-free planar graphs, Discrete Mathematics and Theoretical Computer Science 12(1):87-100, 2010.
   • N. Alon, D. Mubayi, and R. Thomas. Large induced forests in sparse graphs, J. Graph Theory, 38:113-123, 2001.

5. Structural properties of graphs via global discharging procedures
   View DetailsHide Details

   Co-supervised by Benjamin Lévêque and Alexandre Pinlou
   Student: Marthe Bonamy (Master 2 - ENS Lyon)

   Un certain nombre de problèmes de théorie des graphes peuvent se résoudre à l’aide de procédures de déchargement. Le principe est le suivant : (1) des charges sont assignées à certains éléments d’un graphe, (2) une phase de déchargement permet de répartir les charges sur les éléments du graphe, (3) un bilan des charges permet de montrer la propriété souhaitée.

   Cette technique de preuve intervient dans de nombreux résultats, dont le plus célèbre est le Théorème des 4 Couleurs.

   Lors de l’étape (2), la répartition des charges se fait très souvent de manière locale (les éléments adjacents échangent de la charge). En 2005, Borodin a fait évoluer cette technique en introduisant des règles de déchargement global, i.e. des éléments arbitrairement éloignés s’échangent de la charge.

   À ce jour, peu de résultats utilisant le déchargement global ont vu le jour, mais la technique est prometteuse.

   Il faudra dans un premier temps lire les quelques papiers qui utilisent cette nouvelle technique de preuve afin de s’approprier la méthode. Par la suite, nous choisirons quelques résultats sur lesquels nous pourrons travailler (améliorer les bornes inférieures/supérieures, transformer un déchargement local en global, …).

6. Graphs of dimension 4
   View DetailsHide Details

   Co-supervised by Daniel Gonçalves and Alexandre Pinlou
   Student: Arnaud Mary (Master 2 - Univ. Montpellier)

   Le poset d’incidence $P(G)$ d’un graphe $G=(V,E)$ est l’ordre partiel $\le$ sur les éléments de $V\cup E$ tel que $x < y$ implique que $y$ est une arête de $E$ dont $x$ est l’une des extrémités. On observe que si $P(G)$ est de dimension $2$ (c.à.d. que $P(G)$ est l’intersection de 2 ordres totaux) alors $G$ est une forêt de chemins (chaque composante connexe est un chemin). En 1990, W. Schnyder a caractérisé les graphes planaires en terme de dimension de leur poset d’incidence. En effet, un graphe est planaire si et seulement si $P(G)$ est de dimension au plus 3. Plus récemment, S. Felsner a montré que les graphes planaires externes admettent eux aussi une caractérisation simple de leur poset d’incidence. Un graphe $G=(V,E)$ est planaire externe si et seulement si $P(G)$ est l’intersection de 3 ordres totaux, $O_1$, $O_2$ et $O_3$, tels que $O_2 | V = \overline{O_3 | V}$. Cette dernière contrainte, implique l’existence d’une forêt de chemins $F\subseteq G$ telle que $P(F)$ est l’intersection de $O_2 | F$ et $O_3 | F$.

   Plusieurs travaux de recherches portent sur les graphes dont le poset d’incidence est de dimension au plus 4. Le stage portera sur l’étude des graphes $G$ tels que $P(G)$ est l’intersection de 4 ordres totaux, $O_1$, $O_2$, $O_3$ et $O_4$, auxquels on ajoute certaines contraintes. On pourra par exemple demander à ce que $O_2$, $O_3$ et $O_4$ correspondent à une graphe planaire ou à un graphe planaire externe. Il faudra tenter de caractériser ces familles de graphes. Contiennent-elles les 3-arbres, les suspensions de graphes planaires, les graphes linkless embeddable, les graphes sans mineur $K_5$? Sont-elles stables par subdivision d’arêtes, par contraction d’arêtes, par opération $Y-\Delta$ ou $\Delta-Y$ ?

7. Packing chromatic number
   View DetailsHide Details

   Co-supervised by Stéphane Bessy and Alexandre Pinlou
   Student: Cédric Lebrouster (Master 2 – Univ. Montpellier)

   Le concept de packing coloring provient de l’étude des problèmes d’assignations de fréquences dans les réseaux sans fil. En effet, pour éviter les interférences, deux antennes émettrices ne doivent pas avoir la même fréquence si elles sont trop « proches ». Dans certains cas, suivant les fréquences utilisées, ces dernières doivent apparaître de manière plus ou moins dense à travers le réseau.

   La notion de packing coloring est une notion de coloration introduite récemment. On considère un graphe dont les sommets représentent les antennes d’un réseau sans fil. Il existe une arête entre deux sommets de ce graphe si les antennes correspondantes sont trop proches pour recevoir la même fréquence. On souhaite alors colorier les sommets du graphe considéré de sorte que deux sommets adjacents aient des couleurs différentes tout en respectant le fait que deux sommets ayant obtenu la fréquencei soit à distance au moins $i+1$.

   Plus formellement, étant donné un graphe $G=(V,E)$ et un entier $k$, un packing $k$-coloring de $G$ est une fonction $c:V\to \{1,\ldots,k\}$ telle que pour tout $i$ et pour tous sommets $x$ et $y$ avec $c(x)=c(y)=i$, la distance de $x$ à $y$ dans le graphe est au moins $i+1$. Le packing chromatic number de $G$ est alors le plus petit entier $k$ pour lequel $G$ admet un packing $k$-coloring : on note ce nombre $\chi_p(G)$. Lorsque l’on considère une classe de graphes $\mathcal{H}$, on définie $\chi_p(\mathcal{H})=max_{H\in\mathcal{H}}\chi_p(H)$.

   Les trois articles cités dans la bibliographie définissent ce paramètre et fournissent certains résutats. En particulier :

   • $\chi_p(P)=3$ où $P$ est la classe des chemins ;
   • $\chi_p(T_3)=7$ où $T_3$ est la classe des arbres 3-réguliers ;
   • $\chi_p(T_4)=\infty$ où T_4 est la classe des arbres 4-réguliers ;
   • $\chi_p(G_h)=7$ où $G_h$ est la grille hexagonale infinie ;
   • $\chi_p(G_t)=\infty$ où $G_t$ est la grille triangulaire infinie ;
   • $10\leq\chi_p(G_{2d})\leq 22$ où $G_{2d}$ est la grille infinie à 2 dimensions ;
   • $\chi_p(G_{3d})=\infty$ où $G_{3d}$ est la grille infinie a 3 dimensions ;
   • il existe un algorithme en temps polynomial pour déterminer $\chi_p$ pour les cographes et les split graphes.

   Plusieurs questions sont actuellement ouvertes :

   • Si $G$ est un graphe planaire extérieur 3-régulier, le packing chromatic number est-il borné ?
   • Peut-on améliorer la borne supérieure et/ou inférieure du packing chromatic number de la grille à 2 dimensions ?
   • Peut-on borner le packing chromatic number des graphes cubiques en fonction de leur nombre de sommets ?

   Travail attendu:

   • Une étude bibliographique du sujet.
   • Travail de recherche sur les questions ouvertes dans le domaine.
   • Implémentation d’outils pour l’étude de ces questions ouvertes.
   • Rédaction d’un mémoire (LaTeX) et soutenance.

   À priori, pour l’instant, il n’y a pas de financement prévu pour une possible poursuite en doctorat de ce sujet.