  A \emph{star coloring} of a graph $G$ is a proper vertex-coloring such that
no path on four vertices is $2$-colored. The minimum number of colors required
to obtain a star coloring of a graph $G$ is called star chromatic number and it
is denoted by $\chi_s(G)$. A graph $G$ is called $k$-critical if $\chi_s(G)=k$
and $\chi_s(G -e) < \chi_s(G)$ for every edge $e \in E(G)$. In this paper, we
give a characterization of 3-critical, $(n-1)$-critical and $(n-2)$-critical
graphs with respect to star coloring, where $n$ denotes the number of vertices
of $G$. We also give upper and lower bounds on the minimum number of edges in
$(n-1)$-critical and $(n-2)$-critical graphs.
