  We present three new quantum algorithms in the quantum query model for
\textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on
tree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ queries
where $t$ is the treewidth of the graph; \item an algorithm constructed on a
span program that improves a result by Gavinsky and Ito. The algorithm uses
$O(\sqrt{n}+\sqrt{\alpha^{**}})$ queries, where $\alpha^{**}(G)$ is a graph
parameter defined by \[\alpha^{**}(G):=\min_{VC\text{-- vertex cover
of}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\in
I}{\deg{v}}}};\] \item an algorithm for a subclass of circulant graphs that
uses $O(\sqrt{n})$ queries. \end{itemize} We also present an example of a
possibly difficult graph $G$ for which all the known graphs fail to solve graph
collision in $O(\sqrt{n} \log^c n)$ queries.
