Coloração gulosa conexa de grafos livres de H.

Abstract

A proper coloring (with k colors) of a graph G is a function f : V (G) → {1, . . . , k} such that f(u) 6= f(v) for all uv ∈ E(G), and the chromatic number of G is the least integer k to which there is a proper coloring of G with k colors; and it is indicated by χ(G). A proper coloring f is said greedyif it is obtained from a sorting (v 1 , · · · , v n ) of the vertexes of G so that f(v 1 ) = 1 and for each i ∈ {2, . . . , n}, in this order, v i is assigned the lowest color not found in its neighbourhood. Finaly, if the starting order is connected, that is, if N(v i ) ∩ {v 1 , . . . , v i−1 } 6= ∅; then it is said that f is a connected greedy coloring. In 2014, Benevides et. al. showed that, opposing to traditional greedy colorings, not every graph does have a connected greedy coloring (CGC) that requires χ(G) colors. That way the connected greedy number of G is defined as the least such there is a CGC of k colors to G; and it is indicated by χ c (G). Interestingly, also it has been shown it is always possible to obtain a CGC of at most χ(G) + 1 cores, and deciding if χ)c(G) = χ(G) or χ c (G) = χ(G) + 1. is an NP-complete problem. In this work, we investigate the dichotomy of this decision problem for classes of H-free graphs, being H fixed. We show this problem is NP-complete when limited to H-free graphs, if H is not a linear forest or if there is a P 9 as an induced subgraph. Furthermore, we show there is always equality of parameters for P 5 -free graphs and for a subclass of P 6 -free graphs.