  We show two results related to the Hamiltonicity and $k$-Path algorithms in
undirected graphs by Bj\"orklund [FOCS'10], and Bj\"orklund et al., [arXiv'10].
First, we demonstrate that the technique used can be generalized to finding
some $k$-vertex tree with $l$ leaves in an $n$-vertex undirected graph in
$O^*(1.657^k2^{l/2})$ time. It can be applied as a subroutine to solve the
$k$-Internal Spanning Tree ($k$-IST) problem in $O^*(\min(3.455^k, 1.946^n))$
time using polynomial space, improving upon previous algorithms for this
problem. In particular, for the first time we break the natural barrier of
$O^*(2^n)$. Second, we show that the iterated random bipartition employed by
the algorithm can be improved whenever the host graph admits a vertex coloring
with few colors; it can be an ordinary proper vertex coloring, a fractional
vertex coloring, or a vector coloring. In effect, we show improved bounds for
$k$-Path and Hamiltonicity in any graph of maximum degree $\Delta=4,\ldots,12$
or with vector chromatic number at most 8.
