On the Partial Grundy Number of a Graph Minus a Matching - Domingues, Kenny; Silva, Ana (Anais do Encontro de Teoria da Computação (ETC), 2022)
Given a k-coloring S 1 , . . . , S k of G, a vertex in Si is said to be greedy if it has neighbors in S j , for every j < i. Thus, a Grundy coloring can be seen as a coloring where every vertex is greedy. In contrast, a partial Grundy coloring is defined as a coloring in which each color class has at least one greedy vertex; the maximum number of colors in a partial Grundy coloring is denoted by ∂Γ(G). In this paper, we investigate some conjectures about Grundy colorings, already known not to hold, adapted to partial Grundy colorings. We prove that, while two of them also do not hold, a third does. Namely, that given a graph G and a matching M of G, we have that ∂Γ(G) ≤ 2∂Γ(G − M).