Résumé
Temporal graphs are graphs that evolve over time. Many problems which are polynomial-time solvable in standard graphs become NP-hard when appropriately defined in the realm of temporal graphs. This suggested the definition of several parameters for temporal graphs and to prove the fixed-parameter tractability of several problems with respect to these parameters. In this paper, we introduce a hierarchy of parameters based on the previously defined interval membership width and on the temporal evolution of the connected components of the under- lying static graph. We then show that the Eulerian trail problem and the temporal 2-coloring problem are both fixed-parameter tractable (in short, FPT) with respect to any of the parameters in the hierarchy. We also introduce a vertex-variant of the parameters and we show that the firefighter problem (which was known to be FPT with respect to the vertex-variant of the interval membership width) is also FPT with respect to one of the parameters in the second level of the hierarchy.