In this article, stability of uncertain time-delay unforced systems is analyzed through a generalized characteristic quasi-polynomial, which is exactly rewritten as a polytope whose interpolating functions exhibit mutual dependence. It is shown that an adequate combination of Kharitonov-like results and Polya-like relaxations leads to progressively better results at the price of more demanding computational burden. Stability methodologies are developed and proved advantageous when compared with traditional Lyapunov-based approaches, both for structured and unstructured uncertainty.