Connected greedy coloring of [formula omitted]-free graphs.

A connected ordering (v 1 , v 2 , ... , v n) of V (G) is an ordering of the vertices such that v i has at least one neighbor in { v 1 , ... , v i − 1 } for every i ∈ { 2 , ... , 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 χ c (G) such that there exists a CGC of G with χ c (G) colors. An even more interesting fact is that χ c (G) ≤ χ (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ál' et al. in 2001, we are interested in investigating the problems of, given an H -free graph G : (1). deciding whether χ c (G) = χ (G) ; and (2). given also a positive integer k , deciding whether χ c (G) ≤ k. We denote by P t the path on t vertices, and by P t + K 1 the union of P t and a single vertex. We have proved that Problem (2) has the same dichotomy as the coloring problem (namely, 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 χ c (G) = χ (G) always hold when H is an induced subgraph of P 5 or of P 4 + K 1 , and that it is NP -complete to decide whether χ c (G) = χ (G) when H is not a linear forest or contains an induced P 9. We mention that some of the results involve fixed k and fixed χ (G). [ABSTRACT FROM AUTHOR]