What is the maximum number of points at which an $n$-degree polynomial intersects $e^{x^2}$? 
What is the maximum number $\phi(n)$ of roots of the function $e^{x^2}-p(x)$, where $p(x)$ is an $n$-degree polynomial.

It is known that an $n$-degree polynomial intersects the function $e^x$ at at most $n+1$ points (Number of solutions of $P(x)=e^{ax}$ if $P$ is a polynomial). It follows  from the fact that the function $e^x$ has strictly positive $(n+1)$-order derivative whilst $p^{(n+1)}\equiv 0$, so $e^x-p(x)$ has strictly positive $(n+1)$-order derivative.

By inspecting the derivatives of the function $f(x)=e^{x^2}$:
\begin{align*}
  f'(x) &= 2x e^{x^2}, \\
  f''(x) &= 2(2x^2+1)e^{x^2} \\
  f'''(x) &= 4x (2x^2+3) e^{x^2},\\
 & \dots
\end{align*}
we can observe (and prove recursively) that all of the derivatives $f^{n}$ of $f$ are

*

*strictly positive for $n$ even;

*strictly positive on $(0,\infty)$ and strictly negative on $(-\infty,0)$ for  $n$ even.


We can therefore conclude that $f$ intersects any $n$-degree polynomial $p$ at at most $n+1$ points whenever $n$ is odd. And considering interpolation (@GregMartin's comment) we have that:

$\phi(n)=n+1$ for $n$ odd.

However, using the same argument for $n$ even we can only conclude that $f-p$ has at most $n+1$ roots on $(0,\infty)$, and likewise (due to symmetry about $y$-axis) at most $n+1$ points on $(-\infty,0)$. Considering that another intersection might occur at $x=0$, we can be sure that $f$ intersects $p$ at at most $2n+3$ points.

Is there a better estimate than $\phi(n)\leq 2n+3$ for $n$ even?

 A: Promoting the comments to an answer covering the case of even degree polynomials.
In that case we can give the following definite answer:
If $n=2k$ and $\deg p(x)=n$, the number of zeros of $f(x)=e^{x^2}-p(x)$ is at most $n+2$.
From the Taylor expansion of $e^{x^2}$ we can immediately tell that the derivative of order $n+2$,
$$
f^{(n+2)}(x)=D^{n+2}e^{x^2}
$$
is positive for all $x\in\Bbb{R}$. The answer to the linked question then implies that the number of zeros is at most $n+2$.
We also achieve this upper bound with a suitable choice of $p(x)$. Let
$$
p(x)=-A\prod_{i=1}^k(x^2-(2i-1)^2)
$$
with the choice of the positive constant $A$ to be determined in what follows. We see that $p(x)$ has zeros at $-2k+1, -2k+3,\ldots,-1,1,3,\ldots,2k-1$. This means that the sign of $p(x)$ alternates at even integer points: $p(-2k)<0$, $p(-2k+2)>0$
et cetera all the way up to $p(2k)<0$. Clearly the absolute value of all $p(x)$ at all these points is at least $A$. So if we select $A>e^{(2k)^2}+1$, we can deduce that the values of the function
$$f_k(x)=e^{x^2}-A\prod_{i=1}^k(x^2-(2i-1)^2)$$
have the same alternation of signs: $f_k(-2k)<0$, $f_k(-2k+2)>0$, $\ldots$, $f_k(2k)<0$. That is $2k+1$ sign changes, so by continuity $f_k(x)$ has (at least) $2k$ zeros in the interval $[-2k,2k]$. But for large values of $|x|$ the exponential term dominates, and
$$
\lim_{x\to\pm\infty}f_k(x)=+\infty.
$$
By continuity, we thus have (at least) one zero $<-2k$ and one more zero $>2k$ for a total of $2k+2=n+2$.
