  A connected ordering $(v_1, v_2, \ldots, v_n)$ of $V(G)$ is an ordering of
the vertices such that $v_i$ has at least one neighbour in $\{v_1, \ldots, v_{i
- 1}\}$ for every $i \in \{2, \ldots, n\}$. A connected greedy coloring (CGC
for short) is a coloring obtained by applying the greedy algorithm to a
connected ordering. This has been first introduced in 1989 by Hertz and de
Werra, but still very little is known about this problem. An interesting aspect
is that, contrary to the traditional greedy coloring, it is not always true
that a graph has a connected ordering that produces an optimal coloring; this
motivates the definition of the connected chromatic number of $G$, which is the
smallest value $\chi_c(G)$ such that there exists a CGC of $G$ with $\chi_c(G)$
colors. An even more interesting fact is that $\chi_c(G) \le \chi(G)+1$ for
every graph $G$ (Benevides et. al. 2014).
  In this paper, in the light of the dichotomy for the coloring problem
restricted to $H$-free graphs given by Kr\'al et.al. in 2001, we are interested
in investigating the problems of, given an $H$-free graph $G$: (1). deciding
whether $\chi_c(G)=\chi(G)$; and (2). given also a positive integer $k$,
deciding whether $\chi_c(G)\le k$. We have proved that Problem (2) has the same
dichotomy as the coloring problem (i.e., it is polynomial when $H$ is an
induced subgraph of $P_4$ or of $P_3+K_1$, and it is NP-complete otherwise). As
for Problem (1), we have proved that $\chi_c(G) = \chi(G)$ always hold when $G$
is an induced subgraph of $P_5$ or of $P_4+K_1$, and that it is NP-hard to
decide whether $\chi_c(G)=\chi(G)$ when $H$ is not a linear forest or contains
an induced $P_9$. We mention that some of the results actually involve fixed
$k$ and fixed $\chi(G)$.
