  Let $I(G)$ be the edge ideal of a graph $G$ with $|V(G)|=n$ and
$R=\mathbb{K}[x\mid x\in V(G)]$ be a polynomial ring in $n$ variables over a
field $\mathbb{K}$. In this paper we are interested in a conjecture of Eliahou
and Villarreal which states that $\text{pdim}(R/I(G))=\max_{1\leq i \leq
n}\left\{\text{deg}_{G}(x_i)\right\}$ when $G$ is connected and co-chordal. We
show that this conjecture is not true in general. In fact we show that the
difference between $\text{pdim}(R/I(G))$ and $\max_{1\leq i \leq
n}\left\{\text{deg}_{G}(x_i)\right\}$ is not necessarily bounded. For any graph
$G$ we prove that $\max_{1\leq i \leq n}\left\{\text{deg}_{G}(x_i)\right\}\leq
\text{pdim}(R/I(G))$. For a non-increasing sequence of positive integers
$(d_1,d_2,\dots,d_q)$, we define the $(d_1,d_2,\dots,d_q)$-tree graphs. We show
that the independence complex of the complements of these type of trees is
vertex decomposable and quasi-forest. Finally we show that the conjecture is
valid when the complement of $G$ is a $(d_1,d_2,\dots,d_q)$-tree or $G$ has a
full-vertex. To our knowledge the results in this paper generalise all the
existing classes of graphs for which the conjecture is true.
