Graphs decompositions of small width are usually used to solve efficiently problems which are difficult in general. In this thesis, we focus on some limits of these decompositions, and the construction of some obstructions certifying a large width. First, we give a generic algorithm unifying obstructions' construction for several graph widths, in XP time when parameterized by the considered width. In particular, it gives the first algorithm computing efficiently an obstruction to tree-width in time O^{tw+4}. Secondly, we study the parameterized complexity of [Sigma,Rho]-Dominating Set, a generalization of some domination problems characterized by two sets of integers Sigma and Rho. All known studies focused only on cases where this problem is FPT when parameterized by tree-width. In this work, we show that there are some cases where the problem is no longer FPT, and become W[1]-hard instead. Finally, we study the computational complexity of a new coloration problem, named k-Additive Coloring, which combines both graph theory and number theory. We show that this new problem is NP-complete for any fixed number k >= 4, while it can be solved in polynomial time on trees for any k.
