Intitulée : "Problèmes de package, de reconfiguration et d'énumération dans les graphes"
This thesis explores various problems in graph theory, in particular, packing, reconfiguration, and enumeration problems.
Arborescence packing in directed graphs has been extensively studied following the work of Edmonds in 1973 and Frank in 1978. Their results have been generalized in numerous ways, notably for hypergraphs, but also for packings that respect more complex constraints. In this thesis, we will therefore see how to further generalize some of these results, as well as how to transpose them to tree packing, that is, to the case of undirected graphs. The latter were first studied by Nash-Williams and Tutte in 1961, but generalizations of their results are much less common. After improving the result of Bérczi and Frank (2018) for directed graphs on so-called “regular” packages, we show that it is also possible to demonstrate these same results in the undirected case for forest packing. We also show that it is possible to generalize the result of Katoh and Tanigawa (2013) which is about rooted tree packing with a matroid constraint on the roots. This further tighten the gap between the directed and undirected cases. Finally, we consider the generalizations of all these results to hypergraphs and directed hypergraphs, as well as graph augmentation (via the addition of arcs or edges) to obtain the desired packings.
In a second part, we focus on an original problem of graph recoloring. In 2024, Asgarli et al. asked the following question: “Is it possible to recover a graph from a collection of its recoloring graphs?” Although rarely polynomial, the converse is known to be true. In a 2024 paper, Hogan et al. showed that this was possible with only a single reconfiguration graph, provided the number of colors used for it was sufficiently large. We show what the exact value for which a graph can be recovered from its recoloring graph is. We then demonstrate a similar result for recoloring with Kempe changes. Finally, we also consider another classic problem of graph reconfiguration: the reconfiguration of independent sets. We look in particular at the most well-known operations, namely “Token jumping”, “Token sliding”, and “Token addition and removal”.
Finally, in the last chapter, we focus on enumerating the maximal unit interval induced subgraphs of a graph. Based on the “Proximity search” algorithm of Conte and Uno (2019), we propose a lead to demonstrate that it is possible to perform this enumeration with polynomial delay. In particular, we attempt to reuse techniques for the enumeration of chordal graphs, based on the fact that unit interval graphs are a subclass of these graphs with a finite number of obstructions.