$K_4$ would be an example.
A proper vertex-coloring requires 4 colors, and $K_4-v=K_3$ requires only 3 colors, so $K_4$ is vertex critical.
A proper edge-coloring requires 3 colors (verify!), but $K_4-e$ still has a triangle, so $K_4-e$ still requires 3 colors, so $K_4$ is not edge-critical.
EDIT: $K_{2n}$ is an example for any $n\geq2$.
It is obviously vertex-critical. A proper edge-coloring requires $2n-1$ colors (verify!), but $K_{2n}-e$ still requires $2n-1$ colors, since it has maximum degree $2n-1$, so $K_{2n}$ is not edge-critical.
This algorithm is known as "smallest-last coloring"; see, for example, Matula and Beck, Smallest-Last Ordering and Clustering and Graph Coloring Algorithms.
It is not always optimal for planar graphs. The first "slighty-hard" case is the triangular prism, which is 3-colorable, but for which some choices of minimum-degree vertex lead to a 4-coloring. The first hard example is the antiprism graph shown below: it can be verified that although its chromatic number is 4, any way of executing the smallest-last coloring algorithm leads to a 5-coloring. (Kosowski and Manuszewski, Classical coloring of graphs)
I don't know if there are any cases where the smallest-last coloring algorithm will always use 6 colors on a planar graph. I haven't even found any "slightly-hard" cases of this type, though everyone seems to assume that they exist.
However, there are examples where this algorithm will (given unfortunate choices of minimum degree vertex, not for all possible choices) use arbitrarily many colors on a non-planar but bipartite graph (which is 2-colorable). Coleman and Moré, Estimation of sparse Jacobian matrices and coloring problems give the example of a graph on vertex set $\{u_i, v_i, p_i, q_i, r_i, s_i : 1 \le i \le n\}$, with the following edges:
- A complete bipartite graph between $\{p_1, \dots, p_n\}$ and $\{r_1, \dots, r_n\}$;
- A complete bipartite graph between $\{q_1, \dots, q_n\}$ and $\{s_1, \dots, s_n\}$;
- A complete bipartite graph between $\{u_1, \dots, u_n\}$ and $\{v_1, \dots, v_n\}$, with the perfect matching $\{u_1v_1, \dots, u_nv_n\}$ deleted;
- Edges $u_i p_j$ and $v_i q_j$ for all $1 \le i \le j \le n$.
This is shown below for $n=4$:
The bad coloring uses $n+1$ colors and is obtained when coloring vertices in the order $$q_1, s_1, \dots, q_n, s_n,\;p_1, r_1, \dots, p_n, r_n,\;u_1, v_1, \dots, u_n, v_n$$ (that is, deleting vertices in the reverse of that order).
Best Answer
I'm not sure if it's right but here is an example for G:
χ(G) = 3,
ω(G) = 2,
β(G) = 3 and
θ(G) = 3