Analysis of the robust stability of a polynomial with multilinearly dependent coefficient perturbations is presented in this note. Some sufficient conditions for forming a convex polygon with the value set of the polynomials with multilinearly dependent coefficient perturbations are obtained. A zero-exclusion algorithm is then given to determine the D-stability of such polynomials. The well known Kharitonov’s Theorem and the Edge Theorem for stability analysis can be included as special cases of our conclusions.